import std;

alias Edge = Tuple!(int, "node", int, "coin", int, "time");
alias Exchange = Tuple!(int, "coin", int, "time");

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

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

void calc(int n, int s, Edge[][] adj, Exchange[] exchanges) {
    auto q = new MinHeap();
    q.insert(T(0, s, 0));

    int[UsedKey] used;

    auto ans = new long[n];
    ans[] = long.max;
    while (!q.empty) {
        auto t = q.front; q.popFront();

        if (used[UsedKey(t.node, t.coin)]++) continue;
        ans[t.node] = min(ans[t.node], t.time);

        // visited all
        if (ans.all!(e => e < long.max)) break;

        foreach (edge; adj[t.node]) {
            if (t.coin >= edge.coin) {
                q.insert(T(edge.node, t.coin - edge.coin, t.time + edge.time));
            }
        }

        // 全てのノードを回るのに必要な銀貨の枚数は、全ノード数(50) * 銀貨MAX(50) = 2500
        if (t.coin < 2500) {
            // 金貨と銀貨を交換
            q.insert(T(t.node, t.coin + exchanges[t.node].coin, t.time + exchanges[t.node].time));
        }
    }

    foreach (e; ans[1..$]) writeln(e);
}

void main() {
    int n, m, s; scan(n, m, s);
    Edge[][] adj;
    foreach (_; 0..n) adj ~= [[]];
    foreach (_; 0..m) {
        int u, v, a, b; scan(u, v, a, b);
        u--;
        v--;
        adj[u] ~= Edge(v, a, b);
        adj[v] ~= Edge(u, a, b);
    }
    Exchange[] exchanges;
    foreach (_; 0..n) {
        int c, d; scan(c, d);
        exchanges ~= Exchange(c, d);
    }

    calc(n, s, adj, exchanges);
}

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;
