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

fun main(args: Array<String>) {
    val pw = java.io.PrintWriter(System.out)
    Problem.solve(Scanner(System.`in`), pw)
    pw.flush()
}

object Problem {
    data class Line(var to: Int, val c: Int, val d: Int)

    fun solve(sc: Scanner, pw: java.io.PrintWriter) {
        val N = sc.next().toInt()
        val M = sc.next().toInt()
        val S = sc.next().toInt()
        val edge = Array(N) { mutableListOf<Line>() }
        repeat(M) {
            val U = sc.next().toInt() - 1
            val V = sc.next().toInt() - 1
            val A = sc.next().toInt()
            val B = sc.next().toInt()
            edge[U].add(Line(V, A, B))
            edge[V].add(Line(U, A, B))
        }
        val edge2 = Array(N) { Array(2500) { mutableListOf<Line>() } }
        repeat(N) { i ->
            val C = sc.next().toInt()
            val D = sc.next().toInt()
            repeat(2500) { c ->
                edge2[i][c].add(Line(i, min(c + C, 2499), D))
                edge[i].forEach {
                    if (c >= it.c) {
                        edge2[i][c].add(Line(it.to, c - it.c, it.d))
                    }
                }
            }
        }

        val pq = PriorityQueue<Triple<Long, Int, Int>>(100) { x, y ->
            return@PriorityQueue if (y.first < x.first) 1 else -1
        }
        val dist = Array(N) { LongArray(2500) { Long.MAX_VALUE } }
        dist[0][min(S, 2499)] = 0L
        pq.add(Triple(0L, 0, min(S, 2499))) // dist, idx, coin
        while (pq.isNotEmpty()) {
            val tmp = pq.first(); pq.remove(tmp)
            val d = tmp.first
            val from = tmp.second
            val c = tmp.third
            if (dist[from][c] < d) continue
            for (line in edge2[from][c]) {
                if (dist[line.to][line.c] > dist[from][c] + line.d) {
                    dist[line.to][line.c] = dist[from][c] + line.d
                    pq.add(Triple(dist[line.to][line.c], line.to, line.c))
                }
            }
        }

        for (i in 1 until N) {
            pw.println(dist[i].min())
        }
    }
}
