import std;

alias UV = Tuple!(int, "node", int, "a", int, "b");
alias CD = Tuple!(int, "c", int, "d");

alias T = Tuple!(int, "node", int, "cost", int, "coin");
alias MinHeap = BinaryHeap!(Array!T, "a.cost > b.cost");

alias MemoKey = Tuple!(int, "node", int, "coin");

void calc(int n, int s, UV[][] uv, CD[] cd) {

    auto q = new MinHeap;
    q.insert(T(1, 0, s));

    bool[MemoKey] used;

    auto ans = new int[n + 1];
    ans[] = -1;
    while (!q.empty) {
        auto t = q.front; q.popFront();

        if (MemoKey(t.node, t.coin) in used) continue;
        used[MemoKey(t.node, t.coin)] = true;

        if (ans[t.node] == -1)
            ans[t.node] = t.cost;

        // all ok
        bool ok = true;
        for (int i = 1; i <= n; i++) {
            if (ans[i] == -1) {
                ok = false;
                break;
            }
        }
        if (ok) break;

        foreach (u; uv[t.node]) {
            if (t.coin >= u.a) {
                q.insert(T(u.node, t.cost + u.b, t.coin - u.a));
            }
        }
        // 金貨と銀貨を交換
        q.insert(T(t.node, t.cost + cd[t.node].d, t.coin + cd[t.node].c));
    }

    for (int i = 2; i <= n; i++) {
        writeln(ans[i]);
    }
}

void main() {
    int n, m, s; scan(n, m, s);
    UV[][] uv;
    for (int i = 0; i <= n; i++) uv ~= [[]];
    foreach (_; 0..m) {
        int u, v, a, b; scan(u, v, a, b);
        uv[u] ~= UV(v, a, b);
        uv[v] ~= UV(u, a, b);
    }
    auto cd = new CD[n + 1];
    foreach (i; 0..n) {
        int c, d; scan(c, d);
        cd[i+1] = CD(c, d);
    }

    calc(n, s, uv, cd);
}

void scan(T...)(ref T a) {
    string[] ss = readln.split;
    foreach (i, t; T) a[i] = ss[i].to!t;
}
T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;
