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

typedef long long ll;
typedef long double ld;

ll cost[55][55];
ll tajm[55][55];
ll kosta[55];
int vreme[55];

ll n, m, s;

ll dist[55][2505];

const ll INF = 1000000000000000000LL;

vector <ll> graf[55];

void dijkstra(){
    if(s > 50*n) s = 50*n;
    for(ll i=1; i<=n; i++){
        for(ll j=0; j<=50*n; j++){
            dist[i][j] = INF;
        }
    }
    dist[1][s] = 0;
    set <pair <ll, pair <ll, ll>>> q;
    q.insert({0, {1, s}});
    while(!q.empty()){
        auto x = *q.begin();
        q.erase(q.begin());
        ll v = x.second.first;
        ll j = x.second.second;
        ll jos = min(50*n, j+kosta[v]);
        if(dist[v][jos] > dist[v][j] + vreme[v]){
            q.erase({dist[v][jos], {v, jos}});
            dist[v][jos] = dist[v][j] + vreme[v];
            q.insert({dist[v][jos], {v, jos}});
        }
        for(auto c : graf[v]){
            ll jos = j-cost[v][c];
            if(jos < 0) continue;
            if(dist[c][jos] > dist[v][j] + tajm[v][c]){
                q.erase({dist[c][jos], {c, jos}});
                dist[c][jos] = dist[v][j] + tajm[v][c];
                q.insert({dist[c][jos], {c, jos}});
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    cin >> n >> m >> s;
    for(ll i=1; i<=m; i++){
        ll a, b, c, d;
        cin >> a >> b >> c >> d;
        graf[a].push_back(b);
        graf[b].push_back(a);
        cost[a][b] = c;
        tajm[a][b] = d;
        tajm[b][a] = d;
        cost[b][a] = c;
    }
    for(ll i=1; i<=n; i++){
        cin >> kosta[i] >> vreme[i];
    }
    dijkstra();
    for(int i=2; i<=n; i++){
        ll res = dist[i][0];
        for(int j=0; j<=50*n; j++) res = min(res, dist[i][j]);
        cout << res << "\n";
    }
    return 0;
}
