#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define dump(...)
#endif
#define endl "\n"
#define ll long long
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define REPS(i, x) for (int i = 1; i <= (int)(x); i++)
#define RREP(i, x) for (int i = ((int)(x)-1); i >= 0; i--)
#define RREPS(i, x) for (int i = ((int)(x)); i > 0; i--)
#define INF (1 << 30 - 1)
#define LLINF (1LL << 60)
#define vi vector<int>
#define vvi vector<vector<int>>
#define pi pair<int, int>
#define ALL(a) (a).begin(), (a).end()
#define BIT(n) (1LL << (n))
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end()) //sortしてからつかうこと
constexpr ll MOD = 1e9 + 7;
int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};
ll A, B, C, D, E, F, G, H, N, M, L, K, P, Q, R, W, X, Y, Z, S;
string T;
ll ans = 0;

template <typename T>
istream &operator>>(istream &is, vector<T> &vec) {
    for (T &x : vec)
        is >> x;
    return is;
}

//0-indexedに注意
class Graph {
    struct edge {
        int from, to, cost;
        edge(int from, int to, int cost) : from(from), to(to), cost(cost) {}
    };

public:
    int verN;
    int edgeN = 0;
    vector<edge> edge_set;
    vector<vector<pair<int, int>>> adj_list;
    Graph(int verN) : verN(verN), adj_list(verN) {}

    void add_directed_edge(int from, int to, int cost = 1) {
        edge_set.push_back(edge(from, to, cost));
        adj_list[from].push_back(make_pair(to, cost));
        edgeN++;
    }

    void add_undirected_edge(int from, int to, int cost = 1) {
        edge_set.push_back(edge(from, to, cost));
        edge_set.push_back(edge(to, from, cost));
        adj_list[from].push_back(make_pair(to, cost));
        adj_list[to].push_back(make_pair(from, cost));
        edgeN += 2;
    }

    bool bellmanford(int start, vector<int> &d) {
        d.assign(verN, INF);
        for (int i = 0; i < verN; i++) {
            d[i] = INF;
        }
        d[start] = 0;
        for (int i = 0; i < verN; i++) {
            for (int j = 0; j < edgeN; j++) {
                edge e = edge_set[j];
                if (d[e.from] != INF && d[e.to] > d[e.from] + e.cost) {
                    d[e.to] = d[e.from] + e.cost;
                    if (i == verN - 1) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    vector<int> dijkstra(int start) {
        vector<int> d(verN, INF);
        d[start] = 0;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        vector<int> used(verN, 0);
        pq.push(make_pair(0, start));
        while (!pq.empty()) {
            int now = pq.top().second;
            pq.pop();
            used[now] = 1;
            for (auto adj_pair : adj_list[now]) {
                int adj = adj_pair.first;
                int dist = adj_pair.second;
                if (used[adj])
                    continue;
                if (d[adj] > d[now] + dist) {
                    d[adj] = d[now] + dist;
                    pq.push(make_pair(d[adj], adj));
                }
            }
        }
        return move(d);
    }

    vector<vector<int>> warshallfloyd() {
        vector<vector<int>> d(verN, vector<int>(verN, INF));
        for (int i = 0; i < verN; i++) {
            for (auto adj_pair : adj_list[i]) {
                int adj = adj_pair.first;
                int dist = adj_pair.second;
                d[i][adj] = dist;
            }
        }
        for (int i = 0; i < verN; i++) {
            d[i][i] = 0;
        }
        for (int k = 0; k < verN; k++) {         // 経由する頂点
            for (int i = 0; i < verN; i++) {     // 始点
                for (int j = 0; j < verN; j++) { // 終点
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
                }
            }
        }
        return move(d);
    }
};

int intceil(int a, int b) {
    return (a + (b - 1)) / b;
}

signed main() {
    cin >> N >> M >> S;
    vector<vector<int>> w(N, vector<int>(N, INF));
    vector<int> money(N);

    vi a(M), b(M);
    vi c(N), d(N);
    REP(i, M) {
        int u, v;
        cin >> u >> v >> a[i] >> b[i];
        u--, v--;
        w[u][v] = b[i];
        w[v][u] = b[i];
    }
    REP(i, N) {
        cin >> c[i] >> d[i];
        w[i][i] = 0;
    }
    for (int k = 0; k < N; k++) {         // 経由する頂点
        for (int i = 0; i < N; i++) {     // 始点
            for (int j = 0; j < N; j++) { // 終点
                w[i][j] = min(w[i][j], w[i][k] + w[k][j]);
            }
        }
    }
    for (int k = 0; k < N; k++) {     // 経由する頂点
        for (int j = 0; j < N; j++) { // 終点
            int mj = 0;
            int t0j = 0;
            if (w[0][j] > S) {
                int tmp = intceil((w[0][j] - S), c[0]) * c[0] + S;
                t0j = intceil((w[0][j] - S), c[0]) * d[0] + w[0][j];
                mj = tmp - w[0][j];
            } else {
                mj = S - w[0][j];
                t0j = w[0][j];
            }
            int mk = 0;
            int t0k = 0;
            if (w[0][k] > S) {
                int tmp = intceil((w[0][k] - S), c[0]) * c[0] + S;
                t0k = intceil((w[0][j] - S), c[0]) * d[0] + w[0][k];
                mk = tmp - w[0][k];
            } else {
                mk = S - w[0][k];
            }
            int mkj = mk;
            int tkj = 0;
            if (w[0][k] > mkj) {
                int tmp = intceil((w[k][j] - mkj), c[k]) * c[k] + mkj;
                tkj = intceil((w[k][j] - mkj), c[k]) * d[k] + w[k][j];
                mk = tmp - w[k][j];
            } else {
                mkj = mkj - w[k][j];
            }
            if (t0j > t0k + tkj) {
                money[j] = mj;
                w[0][j] = t0j;
            } else {
                money[j] = mkj;
                w[0][j] = tkj;
            }
        }
    }
    REP(i, N) {
        cout << w[0][i] << endl;
    }
}