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

using ll = long long;
using pii = pair<ll, ll>;
using vi = vector<ll>;
using vvi = vector<vi>;

template <class T>
using max_heap = priority_queue<T>;
template <class T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;

template <class T, class U>
void chmax(T &a, U b) {
    if (a < b) a = b;
}
template <class T, class U>
void chmin(T &a, U b) {
    if (b < a) a = b;
}

#define rep(i, j, k) for (int i = j; i < k; i++)
#define all(obj) (obj).begin(), (obj).end()
#define rall(obj) (obj).rbegin(), (obj).rend()
#define debug(x) cerr << #x << ": " << x << endl;
#define debug2(x, y) cerr << #x << ": " << x << ", " << #y << ": " << y << endl;
#define int ll

const ll mod = 1e9 + 7;
const ll inf = (1LL << 60);

ll dp[60][3000];
ll U[110];
ll V[110];
ll A[110];
ll B[110];
ll C[60];
ll D[60];

vi to[60];
pair<int, int> tos[60][60];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(10);
    cout << fixed;

    rep(i, 0, 60) rep(j, 0, 3000) dp[i][j] = inf;
    // memset(dp, inf, 60 * 3000 * sizeof(dp[0][0]));

    int N, M, S;
    cin >> N >> M >> S;
    rep(i, 0, M) {
        int u, v, a, b;
        cin >> u >> v >> a >> b;
        u--, v--;
        U[i] = u;
        V[i] = v;
        A[i] = a;
        B[i] = b;
        to[u].push_back(v);
        to[v].push_back(u);
        tos[u][v] = tos[v][u] = make_pair(A[i], B[i]);
    }
    rep(i, 0, N) {
        int c, d;
        cin >> c >> d;
        C[i] = c;
        D[i] = d;
    }

    // vector<bool> used(N, false);
    rep(i, 0, min(3000LL, S + 1)) dp[0][i] = 0;
    queue<pair<int, int>> que; // u, p
    que.emplace(0, -1);
    while (!que.empty()) {
        auto pa = que.front();
        que.pop();
        int u = pa.first;
        int p = pa.second;
        bool ok = false;
        // debug2(u, p);
        rep(k, 0, 3000) {
            if (p >= 0) {
                // cout << " -- " << u << " " << p << " " << k << " " << k - tos[u][p].first << " " << dp[u][k] << " " << dp[p][k - tos[u][p].first] + tos[u][p].second << " " << (k - tos[u][p].first >= 0) << " " << (dp[u][k] > dp[p][k - tos[u][p].first] + tos[u][p].second) << endl;
                if (k + tos[u][p].first < 3000) {
                    if (dp[u][k] > dp[p][k + tos[u][p].first] + tos[u][p].second) {
                        dp[u][k] = dp[p][k + tos[u][p].first] + tos[u][p].second;
                        // cout << " ok " << u << " " << k << " " << dp[u][k] << endl;
                        // debug2(u, k);
                        // debug(dp[u][k]);
                        ok = true;
                    }
                    // chmin(dp[u][k], dp[p][k - C[u]] + D[u]);
                }
            }
            if (k - C[u] >= 0) {
                if (dp[u][k] > dp[u][k - C[u]] + D[u]) {
                    dp[u][k] = dp[u][k - C[u]] + D[u];
                    ok = true;
                }
            }
            // chmin(dp[u][k], dp[u][k - C[u]] + D[u]);
        }
        if (p != -1 and !ok) continue;

        for (auto v : to[u]) {
            // if (p == v) continue;
            que.emplace(v, u);
        }
    }

    // rep(i, 1, N) {
    //     int ans = inf;
    //     rep(j, 0, 3000) {
    //         cout << i << " " << j << " " << dp[i][j] << endl;
    //     }
    // }

    rep(i, 1, N) {
        int ans = inf;
        rep(j, 0, 3000) chmin(ans, dp[i][j]);
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 5148