#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using P = pair<int,int>;
int MAX = 2500;

vector<vector<P>> hens(55), hen(55 * MAX);
vector<int> sil(100), tim(100);
vector<int> c(55), d(55);//銀貨のレート　時間

int value(int i, int s) {
    return i * MAX + s;
}

vector<ll> dijkstra(int s) {

    vector<ll> dist(hen.size(), 1e15);
    priority_queue<P, vector<P>, greater<P>> que;
    que.emplace(0, s);
    dist[s] = 0;

    while(!que.empty()) {
        auto d = que.top().first;
        auto v = que.top().second;
        que.pop();
        if(dist[v] < d)continue;


        for(auto i : hen[v]) {
            int to = i.first;  //行き先の頂点
            int di = i.second; //時間

            if(dist[to] > dist[v] + di) {

                dist[to] = dist[v] + di;
                que.emplace(dist[to], to);

            }
        }

    }
    return dist;
}


int main()
{
    int n, m, s;
    cin >> n >> m >> s;
    s = min(s, MAX - 1);
    
    for(int i = 0; i < m; i++) {
        int u, v, a, b; cin >> u >> v >> a >> b; u--,v--;
        hens[u].push_back({v, i});
        hens[v].push_back({u, i});
        sil[i] = a; tim[i] = b;
    }

    for(int i = 0; i < n; i++) {
        int x, y; cin >> x >> y;
        c[i] = x; d[i] = y;
    }

    //頂点を増やす

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < MAX; j++) {
            int nxt = j + c[i];
            nxt = min(nxt, MAX - 1);
            hen[value(i, j)].emplace_back(value(i, nxt), d[i]);

            for(auto k: hens[i]) {
                int nxt = j - sil[k.second];
                if(nxt < 0)continue;
                hen[value(i, j)].emplace_back(value(k.first, nxt), tim[k.second]);
            }
        }
    }

    auto dist = dijkstra(value(0, s));


    for(int i = 1; i < n; i++) {
    
        cout << *min_element(dist.begin() + value(i, 0), dist.begin() + value(i + 1, 0)) << endl;
        //for(int j = 0; j < MAX; j++) {}
    }

}