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

struct Cost {
    int64_t silver;
    int64_t time;
};

struct Adj {
    int dest;
    Cost cost;
    Adj(int _d, const Cost &_c):dest(_d),cost(_c){}
};

struct State {
    int city;
    int64_t silver;
    int64_t time;
    int64_t maxSilverCost;

    State(int _c, int64_t _s, int64_t _t, int64_t _max)
        :city(_c), silver(_s), time(_t), maxSilverCost(_max) {}

    bool operator < (const State &s) const {
        return time > s.time || (time == s.time && silver < s.silver);
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int nCities, nRoads;
    int64_t initSilvers;
    cin >> nCities >> nRoads >> initSilvers;

    int64_t maxSilverCost = 0;
    vector<vector<Adj>> adj(nCities + 1);
    for (int i = 0; i < nRoads; ++i) {
        int u, v;
        Cost c;
        cin >> u >> v >> c.silver >> c.time;
        adj[u].push_back(Adj(v, c));
        adj[v].push_back(Adj(u, c));
        maxSilverCost += c.silver;
    }
    maxSilverCost <<= 1;
    initSilvers = min(initSilvers, maxSilverCost);

    vector<Cost> cityCost(nCities + 1);
    for (int i = 1; i <= nCities; ++i) {
        cin >> cityCost[i].silver;
        cin >> cityCost[i].time;
    }

    priority_queue<State> pq;
    State initState(1, initSilvers, 0, maxSilverCost);
    vector<int64_t> minTime(nCities + 1, numeric_limits<int64_t>::max());
    vector<vector<int64_t>> dp(nCities + 1, vector<int64_t>(maxSilverCost + 1, numeric_limits<int64_t>::max()));

    while (1) {
        pq.push(initState);
        dp[1][initState.silver] = initState.time;
        if (initState.silver == maxSilverCost) break;
        initState.silver += cityCost[1].silver;
        if (initState.silver > maxSilverCost)
            initState.silver = maxSilverCost;
        initState.time += cityCost[1].time;
    }

    int completed = 0;

    while (!pq.empty()) {
        auto state = pq.top();
        pq.pop();
        if (state.time < minTime[state.city]) {
            ++completed;
            minTime[state.city] = state.time;
            if (completed == nCities) break;
        }

        for (const auto &next : adj[state.city]) {
            auto newState = state;
            newState.city = next.dest;
            newState.silver -= next.cost.silver;
            newState.time += next.cost.time;
            newState.maxSilverCost -= next.cost.silver;
            if (newState.maxSilverCost < 0) continue;

            while (1) {
                if (newState.silver >= 0) {
                    if (newState.time < dp[newState.city][newState.silver]) {
                        pq.push(newState);
                        dp[newState.city][newState.silver] = newState.time;
                    }
                }
                if (newState.silver == newState.maxSilverCost) break;
                newState.silver += cityCost[state.city].silver;
                if (newState.silver > newState.maxSilverCost)
                    newState.silver = newState.maxSilverCost;
                newState.time += cityCost[state.city].time;
            }
        }
    }

    for (int i = 2; i <= nCities; ++i) {
        cout << minTime[i] << endl;
    }

    return 0;
}

Measured memory_bytes: 136248