#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rep2(i,s,f) for(int i=s;i<f;i++)
#define INF 1000000000000000000
#define MOD 1000000007
#define endl "\n"
#define fcout cout<<fixed<<setprecision(15)
typedef pair<int, int> P;
//struct edge { int to, cost; };

template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }

bool prime(int n) {
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0)return false;
    }
    return n != 1;
}
int gcd(int x, int y) {
    if (y == 0)return x;
    return gcd(y, x % y);
}
int lcm(int x, int y) {
return x / gcd(x, y) * y;
}
int mod_pow(int n, int p, int m) {
    if (p == 0) return 1;
    if (p % 2 == 0) {
        int t = mod_pow(n, p / 2, m);
        return (t * t) % m;
    }
    return n * mod_pow(n, p - 1, m) % m;
}
int extGCD(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long d = extGCD(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
int modinv(int a, int m) {
    int b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
int modinv2(int a, int mod) {
    return mod_pow(a, mod - 2, mod);
}
int digit(int x) {
    int cnt = 0;
    while (x > 0) {
        cnt += x % 10;
        x /= 10;
    }
    return cnt;
}
int read() {
    int tmp;
    cin >> tmp;
    return tmp;
}
int xor128() {
    static int x = 123456789, y = 362436069, z = 521288629, w = 88675123;
    int t = (x xor (x << 11));
    x = y; y = z; z = w;
    return (w = (w xor (w >> 19)) xor (t xor (t >> 8)));
}
map<int, int> factaring(int x) {
    map<int, int>ans;
    int now = 2;
    while (now * now <= x) {
        if (x % now == 0) {
            x /= now;
            ans[now]++;
        }
        else now++;
    }
    if (x != 1) ans[x]++;
    return ans;
}
int comb(int n, int k, int mod) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    k = min(k, n - k);
    int x = 1, y = 1;
    rep(i, k) {
        y *= i + 1;
        y %= mod;
    }
    for (int i = n - k + 1; i <= n; i++) {
        x *= i;
        x %= mod;
    }
    return x * modinv(y, mod) % mod;
}

string s;
int dp[2][2025];

signed main() {
    //srand((unsigned)time(NULL));

    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int n, m, start_silver;
    vector<int> froms, tos, costs, times;
    int change_silver[55], change_time[55];
    int shortest[55][10005];

    cin >> n >> m >> start_silver;
    rep(i, m) {
        int u, v, a, b;
        cin >> u >> v >> a >> b;
        u--, v--;
        froms.push_back(u); froms.push_back(v);
        tos.push_back(v), tos.push_back(u);
        costs.push_back(a); costs.push_back(a);
        times.push_back(b); times.push_back(b);
    }
    rep(i, n) {
        cin >> change_silver[i] >> change_time[i];
    }

    rep(i, n) {
        rep(j, 10001) {
            shortest[i][j] = INF;
        }
    }
    rep(i, min((int)10001, start_silver + 1)) {
        shortest[0][i] = 0;
    }

    while (1) {
        rep(i, n) {
            rep(j, 10001) {
                chmin(shortest[i][j], shortest[i][max((int)0, j - change_silver[i])] + change_time[i]);
            }
        }

        bool update = false;
        rep(i, 2 * m) {
            for (int j = costs[i]; j <= 10000; j++) {
                if (chmin(shortest[tos[i]][j - costs[i]], shortest[froms[i]][j] + times[i])) {
                    update = true;
                }
            }
        }
        if (!update) break;
    }
    for (int i = 1; i < n; i++) {
        int ans = INF;
        rep(j, 10001) {
            chmin(ans, shortest[i][j]);
        }
        cout << ans << endl;
    }

    return 0;
}


Measured memory_bytes: 7584