import std.stdio, std.string, std.conv, std.range;
import std.algorithm, std.array, std.typecons, std.container;
import std.math, std.numeric, std.random, core.bitop;

enum inf = 1_001_001_001;
enum infl = 1_001_001_001_001_001_001L;

auto dijkstra(Edge[][] adj, int s) {
    alias Pair = Tuple!(int, "num", long, "dist");

    int N = adj.length.to!int;

    auto dist = new long[](N);
    dist[] = infl;
    dist[s] = 0;

    auto q = BinaryHeap!(Array!Pair, "a.dist > b.dist")();
    q.insert(Pair(s, 0));

    int rep = N - 1;

    while (!q.empty && rep) {
        auto v = q.front;
        q.popFront();

        if (dist[v.num] < v.dist)
            continue;

        rep--;

        foreach (e; adj[v.num]) {
            if (dist[e.to] > dist[v.num] + e.cost) {
                dist[e.to] = dist[v.num] + e.cost;
                q.insert(Pair(e.to, dist[e.to]));
            }
        }
    }

    return dist;
}

alias Edge = Tuple!(int, "to", int, "cost");

void main() {
    int n, m, s;
    scan(n, m, s);

    const mn = 50 * n + 1;
    chmin(s, mn - 1);

    auto adj = new Edge[][](n * mn, 0);
    foreach (i; 0 .. m) {
        int ui, vi, ai, bi;
        scan(ui, vi, ai, bi);
        ui--, vi--;
        foreach (j; 0 .. mn) {
            if (j - ai >= 0) {
                assert(j * n + ui < n * mn);
                assert(j * n + vi < n * mn);
                assert((j - ai) * n + vi >= 0);
                assert((j - ai) * n + ui >= 0);
                adj[j * n + ui] ~= Edge((j - ai) * n + vi, bi);
                adj[j * n + vi] ~= Edge((j - ai) * n + ui, bi);
            }
        }
    }

    foreach (i; 0 .. n) {
        int ci, di;
        scan(ci, di);
        foreach (j; 0 .. mn) {
            if (j + ci >= mn) break;
            assert((j + ci) * n + i < n * mn);
            adj[j * n + i] ~= Edge((j + ci) * n + i, di);
        }
    }

    debug {
        // writefln("%(%s\n%)", adj);
    }

    auto dist = dijkstra(adj, s * n + 0);
    auto ans = new long[](n);
    ans[] = infl;
    foreach (i; 1 .. n) {
        foreach (j; 0 .. mn) {
            chmin(ans[i], dist[j * n + i]);
        }
    }
    writefln("%(%s\n%)", ans[1..$]);
}

void scan(T...)(ref T args) {
    auto line = readln.split; // @suppress(dscanner.suspicious.unmodified)
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront;
    }
    assert(line.empty);
}

void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}

bool chmin(T, U...)(ref T x, U args) {
    bool isChanged;
    foreach (arg; args)
        if (x > arg) {
            x = arg;
            isChanged = true;
        }
    return isChanged;
}

bool chmax(T, U...)(ref T x, U args) {
    bool isChanged;
    foreach (arg; args)
        if (x < arg) {
            x = arg;
            isChanged = true;
        }
    return isChanged;
}

void yes(bool ok, string y = "Yes", string n = "No") {
    return writeln(ok ? y : n);
}
