/* dijkstra.cpp
    ダイクストラ法で、ある頂点から各頂点への最短距離を求めるアルゴリズム
    負の辺が含まれる場合はうまく計算出来ないので、ベルマンフォード法を用いる

    verified: AOJ GRL_1_A
        http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A&lang=jp
*/

#include <bits/stdc++.h>
using namespace std;

template <typename T>
struct Edge {
    int to;
    T cost;
};
using Graph = vector<vector<Edge<long long>>>;  // 距離/コストの型 T を指定する
const long long INF = (1LL << 60);              // 型 T のINF (完全な最大値は取らないように)

using ll = long long;

int S;

/* dijkstra(G,s,dis,prev)
    入力：グラフ G, 開始点 s, 距離を格納する dis, 最短経路の前の点を記録するprev
    計算量：O(|E|log|V|)
    副作用：dis, prevが書き換えられる
*/
template <typename T>
void dijkstra(const Graph &G, int s, vector<T> &dis, vector<int> &prev) {
    using P = pair<T, int>;

    int N = G.size();
    dis.resize(N, INF);
    prev.resize(N, -1);
    priority_queue<P, vector<P>, greater<P>> pq;  // the least element is top. first:cost, second: node
    dis[s] = 0;
    pq.emplace(dis[s], s);
    while (!pq.empty()) {
        P p = pq.top();  // the least element
        pq.pop();
        int v = p.second;
        if (dis[v] < p.first) {
            continue;
        }
        for (auto &e : G[v]) {
            if (dis[e.to] > dis[v] + e.cost) {
                dis[e.to] = dis[v] + e.cost;
                prev[e.to] = v;
                pq.emplace(dis[e.to], e.to);
            }
        }
    }
}

int main() {
    int N, M;
    cin >> N >> M >> S;
    Graph G(N * 2501);
    for (int i = 0; i < M; i++) {
        int u, v, a, b;
        cin >> u >> v >> a >> b;
        u--, v--;
        for (int j = 0; j < 2501; j++) {
            if (j - a >= 0) G[u * 2501 + j].push_back({v * 2501 + (j - a), b});
            if (j - a >= 0) G[v * 2501 + j].push_back({u * 2501 + (j - a), b});
        }
    }
    for (int u = 0; u < N; u++) {
        int c;
        ll d;
        cin >> c >> d;
        for (int j = 0; j < 2501 - 1; j++) {
            G[u * 2501 + j].push_back({u * 2501 + min(j + c, 2501 - 1), d});
        }
    }
    vector<long long> dis;
    vector<int> prev;
    dijkstra(G, min(S, 2500), dis, prev);
    for (int i = 1; i < N; i++) {
        ll ans = INF;
        for (int j = 0; j < 2501; j++) {
            ans = min(ans, dis[i * 2501 + j]);
        }
        cout << ans << endl;
    }

    return 0;
}
