#include <algorithm>
#include <cmath>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

typedef long long ll;

#define el '\n'
#define rep(i, a, b) for (int i = a; i < b; i++)
#define repi(i, a, b) for (int i = a; i >= b; i--)
#define vi vector<int>
#define vvi vector<vector<int>>
#define vii vector<pair<int, int>>
#define vvii vector<vector<pair<int, int>>>
#define vll vector<ll>
#define vvll vector<vector<ll>>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mp make_pair
#ifdef LOCAL
#define debug(fmt, ...) printf(fmt, ##__VA_ARGS__)
#define check(...) assert(__VA_ARGS__)
#else
#define debug(fmt, ...)
#define check(...)
#endif

#define INF 1000000000000000
#define MAX_SILVER_NEEDED (ll)(50 * 100)

struct road_info {
    int u, v, a, b;
};

int n, m, s;
vector<vector<road_info>> adj;
vii exch;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> s;
    adj = vector<vector<road_info>>(n);
    rep(i, 0, m) {
        int u, v, a, b;
        cin >> u >> v >> a >> b;
        u--, v--;
        adj[u].push_back({u, v, a, b});
        adj[v].push_back({v, u, a, b});
    }
    exch = vii(n);
    rep(i, 0, n) {
        cin >> exch[i].first >> exch[i].second;
    }
    // vii nodes;
    // rep(i, 0, n) {
    //     rep(coin, 0, MAX_SILVER_NEEDED + 1) {
    //         nodes.push_back({i, coin});
    //     }
    // }
    int max_silver_needed = (n - 1) * 50;
    vvll shortest(n, vll(max_silver_needed + 1, INF));
    s = min(s, max_silver_needed);
    shortest[0][s] = 0;
    // city, coin
    auto cmp = [&](pii a, pii b) {
        ll s1 = shortest[a.first][a.second];
        ll s2 = shortest[b.first][b.second];
        return s1 < s2 || (s1 == s2 && a < b);
    };
    set<pii, decltype(cmp)> q(cmp);
    q.insert({0, s});
    debug("here");
    vll ans(n, INF);
    ans[0] = 0;
    while (!q.empty()) {
        pii h = *q.begin();
        int city = h.first;
        int silver = h.second;
        q.erase(q.begin());
        ans[city] = min(ans[city], shortest[city][silver]);
        debug("city=%d,silver=%d,shortest=%lld\n", city, silver, shortest[city][silver]);
        for (auto next : adj[city]) {
            ll more_time = 0;
            ll more_silver = 0;
            while (true) {
                debug("next city=%d,silver=%d,more_silver=%lld,more_time=%lld\n", next.v, silver, more_silver, more_time);
                bool reach_max = false;
                if (silver + more_silver >= next.a) {
                    int silver2 = min((ll)max_silver_needed, silver + more_silver - next.a);
                    reach_max = silver2 == max_silver_needed;
                    ll t = shortest[city][silver] + more_time + next.b;
                    if (t < shortest[next.v][silver2]) {
                        pii node = {next.v, silver2};
                        q.erase(node);
                        shortest[next.v][silver2] = t;
                        q.insert(node);
                    }
                }
                if (reach_max) {
                    break;
                }
                more_silver += exch[city].first;
                more_time += exch[city].second;
            }
        }
    }

    rep(i, 1, n) {
        cout << ans[i] << el;
    }
}


Measured memory_bytes: 9272