//ABC164-E
//拡張ダイクストラ

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
#define int int64
#define rep(i, n) for(int i=0; i<n; i++)
#define FOR(i, a, b) for(int i=a; i<b; i++)
#define SORT(x) sort(x.begin(), x.end())
#define GSORT(x) sort(x.begin(), x.end(), greater<int>())
#define mk make_pair
#define fi first
#define se second
#define pb push_back
#define ALL(x) x.begin(), x.end()
#define V(T) vector<T>
typedef pair<int, int> P;
typedef pair<int, P> Pp;
typedef pair<P, P> PP;
typedef vector<int> vi;
typedef vector<vi> vvi;
int max(int a, int b) {if(b>a) return b; else return a;}
int min(int a, int b) {if(b<a) return b; else return a;}

const int INF = 1e18;

//銀貨はこれ以上持たなくてよい（最大制約下でも余る）
const int MAX = 2500;

//辺の構造体（次の頂点、運賃、移動時間）
typedef struct Edge{
    int u, c, t;
} Edge;

V(V(Edge)) G(55);
vi C(55), D(55);

//各頂点について、所持している銀貨の枚数ごとの移動時間を記録する
vvi dist(55, vi(MAX, INF));

void dijkstra(int S) {
    S = min(S, MAX);
    dist[0][S] = 0;
    priority_queue<Pp, V(Pp), greater<Pp>> q;
    q.push(Pp(0, P(0, S)));

    while(!q.empty()) {
        Pp p = q.top(); q.pop();
        int v = p.se.fi, d = p.fi, s = p.se.se;
        if(d > dist[v][s]) continue;

        //銀貨の補充は、自分自身への移動と考える
        if(s+C[v] <= MAX) {
            if(d+D[v] < dist[v][s+C[v]]) {
                dist[v][s+C[v]] = d+D[v];
                q.push(Pp(d+D[v], P(v, s+C[v])));
            }
        }

        //通常のダイクストラ
        rep(i, G[v].size()) {
            int nv = G[v][i].u;
            int nd = d + G[v][i].t;
            int ns = s - G[v][i].c;
            if(ns<0) continue;
            if(nd < dist[nv][ns]) {
                dist[nv][ns] = nd;
                q.push(Pp(nd, P(nv, ns)));
            }
        }
    }
}



signed main() {
    int N, M, S;
    cin >> N >> M >> S;
    rep(i, M) {
        int u, v, a, b;
        cin >> u >> v >> a >> b;
        u--; v--;
        G[u].pb(Edge{v, a, b});
        G[v].pb(Edge{u, a, b});
    }
    rep(i, N) cin >> C[i] >> D[i];

    dijkstra(S);

    FOR(i, 1, N) {
        int res = INF;
        rep(j, MAX) {
            res = min(res, dist[i][j]);
        }
        cout << res << endl;
    }

    return 0;
}