#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;

ll S;

struct Road {
    ll coin;
    ll time;
};

bool operator<(const Road& x0, const Road& x1) { return x0.time == x1.time ? x0.coin > x1.coin : x0.time < x1.time; }

template <typename T>
struct Graph {
    int V, E;
    struct Edge {
        int from, to;
        T cost;
    };
    vector<vector<Edge>> edge;
    vector<vector<T>> dist;
    vector<Edge> es;

    Graph(int V, int E) : V(V), E(E) {
        edge.assign(V, vector<Edge>(0));
        dist.resize(V, vector<T>(0));
    }

    void input(bool is_direct, bool inputc, bool index0 = false) {
        int a, b;
        T c = 0;
        for (int i = 0; i < E; i++) {
            cin >> a >> b;
            if (inputc) cin >> c;
            if (!index0) a--, b--;
            edge[a].push_back((Edge){a, b, c});
            es.push_back((Edge){a, b, c});
            if (!is_direct) {
                edge[b].push_back((Edge){b, a, c});
                es.push_back((Edge){b, a, c});
            }
        }
        if (!is_direct) E *= 2;
    }

    void add_edge(int from, int to, T cost, bool is_direct) {
        edge[from].push_back({from, to, cost});
        es.push_back({from, to, cost});
        if (!is_direct) {
            edge[to].push_back({to, from, cost});
            es.push_back({to, from, cost});
            E++;
        }
        E++;
    }

    typedef pair<T, int> P;  // (first,second) := (最短距離,頂点番号)
    // 頂点rからの最小距離
    void dijkstra(int r = 0) {
        dist[r].assign(V, {-INF, INF});

        priority_queue<P, vector<P>, greater<P>> que;
        que.push(P({S, 0}, r));
        dist[r][r] = {S, 0};

        while (que.size()) {
            P p = que.top();
            que.pop();
            int v = p.second;
            if (dist[r][v] < p.first) continue;
            for (int i = 0; i < edge[v].size(); i++) {
                Edge e = edge[v][i];
                T add = {dist[r][v].coin + e.cost.coin, dist[r][v].time + e.cost.time};
                if (add.coin < 0) continue;
                if (add < dist[r][e.to]) {
                    dist[r][e.to] = add;
                    que.push(P(dist[r][e.to], e.to));
                }
            }
        }
    }
};

int main() {
    int N, M;
    cin >> N >> M >> S;
    Graph<Road> g(N * 5010, 0);
    for (int i = 0; i < M; i++) {
        int u, v;
        Road r;
        cin >> u >> v >> r.coin >> r.time;
        r.coin *= -1;
        u--, v--;
        for (int j = 0; j < 5010; j++) {
            g.add_edge(u + j * N, v + j * N, r, false);
        }
    }
    for (int i = 0; i < N; i++) {
        ll C, D;
        cin >> C >> D;
        for (int j = 1; j < 5010; j++) {
            g.add_edge(i + (j - 1) * N, i + j * N, {C, D}, true);
        }
    }
    g.dijkstra();
    for (int i = 1; i < N; i++) {
        ll ans = INF;
        for (int j = 0; j < 5010; j++) ans = min(ans, g.dist[0][i + j * N].time);
        cout << ans << endl;
    }
    return 0;
}