import java.io.PrintWriter
import java.util.ArrayDeque
import kotlin.math.min

data class Train(val dest: Int, val fee: Int, val time: Long)
data class Exchange(val currency: Int, val time: Long)
data class State(val city: Int, val money: Int, val time: Long)

fun main() {
    val pw = PrintWriter(System.out)

    val upper = 2500

    val (n, m, s) = readInputLine().split(" ").map { it.toInt() }

    val cost = Array(n) { LongArray(upper + 1) { Long.MAX_VALUE } }

    val edges = Array(n) { mutableListOf<Train>() }

    repeat(m) {
        val input = readInputLine().split(" ")
        val u = input[0].toInt() - 1
        val v = input[1].toInt() - 1
        val a = input[2].toInt()
        val b = input[3].toLong()
        edges[u].add(Train(v, a, b))
        edges[v].add(Train(u, a, b))
    }

    val exchange = Array(n) {
        val input = readInputLine().split(" ")
        Exchange(input[0].toInt(), input[1].toLong())
    }

    cost[0][min(upper, s)] = 0L

    val queue = ArrayDeque<State>()

    queue.add(State(0, min(upper, s), 0L))

    while (queue.isNotEmpty()) {
        val state = queue.poll()!!

        for (e in edges[state.city]) {
            if (state.money >= e.fee) {
                if (cost[e.dest][state.money - e.fee] > state.time + e.time) {
                    cost[e.dest][state.money - e.fee] = state.time + e.time
                    queue.add(State(e.dest, state.money - e.fee, state.time + e.time))
                }
            }
        }

        val ex = exchange[state.city]

        if (cost[state.city][min(upper, state.money + ex.currency)] > state.time + ex.time) {
            cost[state.city][min(upper, state.money + ex.currency)] = state.time + ex.time
            queue.add(State(state.city, min(upper, state.money + ex.currency), state.time + ex.time))
        }
    }

    for (i in 1 until n) {
        pw.println(cost[i].min())
    }

    pw.flush()
}

fun readInputLine(): String {
    return readLine()!!
}
