#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define ALL(v) (v).begin(), (v).end()
using ll = long long;
using P = pair<int, int>;
constexpr int INF = 1e9;
constexpr long long LINF = 1e18;
constexpr long long MOD = 1e9 + 7;

#define MAX 1000

signed main() {
    int n, m, s;
    cin >> n >> m >> s;
    using T = tuple <ll, ll, ll>;
    vector<T> G[n];
    int u, v, a, b;
    rep(i, m) {
        cin >> u >> v >> a >> b;
        u--;
        v--;
        G[u].emplace_back(v, a, b);
        G[v].emplace_back(u, a, b);
    }
    ll c[n], d[n];
    rep(i, n) {
        cin >> c[i] >> d[i];
    }
    ll dist[n][MAX + 1];
    fill(dist[0], dist[n], LINF);
    priority_queue<T, vector<T>, greater<T>> que;
    for (int j = 0;; j++) {
        int nxt = min(s + c[0] * j, (ll)MAX);
        dist[0][nxt] = d[0] * j;
        que.emplace(dist[0][nxt], nxt, 0);
        if (s + c[0] * j > MAX) break;
    }
    while (!que.empty()) {
        T t = que.top();
        que.pop();
        int cnt = get<1>(t), v = get<2>(t);
        if (dist[v][cnt] < get<0>(t)) continue;
        for (int i = 0; i < G[v].size(); i++) {
            int to = get<0>(G[v][i]), need = get<1>(G[v][i]);
            ll cost = get<2>(G[v][i]);
            for (int j = 0;; j++) {
                if (cnt - need < 0) break;
                int nxt = min(cnt - need + c[to] * j, (ll)MAX);
                if (dist[to][nxt] > dist[v][cnt] + cost + d[to] * j) {
                    dist[to][nxt] = dist[v][cnt] + cost + d[to] * j;
                    que.emplace(dist[to][nxt], nxt, to);
                }
                if (cnt - need + c[to] * j > MAX) break;
            }
        }
    }
    for (int v = 1; v < n; v++){
        ll ans = LINF;
        for (int j = 0; j <= MAX; j++) {
            ans = min(ans, dist[v][j]);
        }
        cout << ans << endl;
    }
    return 0;
}