import java.util.*
import kotlin.math.min

data class Edge(val to: Int, val fee: Int, val time: Int)
fun main() {
    val (n, m, s) = readLine()!!.trim().split(' ').map(String::toInt)
    val stations = List(n){mutableListOf<Edge>()}
    repeat(m){
        val (u, v, a, b) = readLine()!!.trim().split(' ').map(String::toInt)
        stations[u - 1].add(Edge(v - 1, a, b))
        stations[v - 1].add(Edge(u - 1, a, b))
    }
    val exchanger = List(n){
        val (c, d) = readLine()!!.trim().split(' ').map(String::toInt)
        c to d
    }
    val maxCost = stations.sumBy{ it.sumBy(Edge::fee) } / 2
    val minCost = Array(n){LongArray(maxCost + 1){Long.MAX_VALUE} }.also{it[0][min(s, maxCost)] = 0}
    val queue = PriorityQueue<Pair<Pair<Int, Int>, Long>>(compareBy(Pair<*, Long>::second)).also{it.add(Pair(0 to min(s, maxCost), 0))}
    while (queue.isNotEmpty()) {
        val (pair, time) = queue.poll()
        val (current, silver) = pair
        if (minCost[current][silver] != time) continue
        for ((next, fee, duration) in stations[current]) if (fee <= silver) {
            if (minCost[next][silver - fee] > time + duration) {
                minCost[next][silver - fee] = time + duration
                queue.add(Pair(next to silver - fee, time + duration))
            }
        }
        val (silverDiff, duration) = exchanger[current]
        if (minCost[current][min(silver + silverDiff, maxCost)] > time + duration) {
            minCost[current][min(silver + silverDiff, maxCost)] = time + duration
            queue.add(Pair(current to min(silver + silverDiff, maxCost), time + duration))
        }
    }
    println(
        minCost.drop(1).joinToString("\n"){it.min()!!.toString()}
    )
}
