#pragma GCC optimize("O3", "unroll-loops")
//#pragma GCC target("avx2")
//#pragma GCC target ("sse4")
#pragma optimize("fast-math")

#include <bits/stdc++.h>
#include <stdio.h>

using namespace std;
#define endl '\n'
#define ull unsigned long long
#define si short int
#define ll long long
#define ld long double
#define pb push_back
#define pii pair<int, int>
#define pdd pair<double, double>
#define pil pair<int, ll>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define piii pair<pair<int, int>, int>
#define all(vec) (vec).begin(), (vec).end()
#define rall(vec) (vec).rbegin(), (vec).rend()
#define piiii pair<pair<int, int>, pair<int, int>>


ll mun(ll a, ll b){
    if(a>b) return b;
    else return a;
}


unsigned int beg_time = clock();
void solve() {
    int n,m,s;
    cin>>n>>m>>s;
    static ll dp[2][2501][51];
    ll inf =1e18;
    for(int i=0;i<2;i++){
        for(int j=0;j<2501;j++){
            for(int k=0;k<51;k++){
                dp[i][j][k]=inf;
            }
        }
    }
    for(int i=0;i<=min(s, 2500);i++) dp[0][i][1]=0;
    pll dist[51][51];
    for(int i=0;i<51;i++){
        for(int j=0;j<51;j++){
            dist[i][j]={inf, inf};
        }
    }

    vector<pii> edges;
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        int a,b;
        cin>>a>>b;
        edges.pb({u,v});
        edges.pb({v,u});
        dist[u][v]={-a,b};
        dist[v][u]={-a,b};
    }

    vector<pii> town(n+1);
    for(int i=1;i<n+1;i++){
        cin>>town[i].first>>town[i].second;
        edges.pb({i,i});
        dist[i][i]=town[i];
    }
    static ll ans[51];
    for(int i=0;i<51;i++){
        ans[i]=inf;
    }

    for(int i=0;i<2500;i++){
        for(int j=0;j<2501;j++){
            for(auto &p:edges){
                if(dp[0][j][p.first]== inf) continue;
                if(j+dist[p.first][p.second].first<0) continue;
                dp[1][min(j+dist[p.first][p.second].first, (ll)2500)][p.second]=mun(dp[1][mun(j+dist[p.first][p.second].first, (ll)2500)][p.second], dp[0][j][p.first]+dist[p.first][p.second].second);
                ans[p.second]=mun(ans[p.second], dp[1][mun(j+dist[p.first][p.second].first, (ll)2500)][p.second]);
            }
        }
        for(int j=0;j<2501;j++){
            for(int k=0;k<n+1;k++){
                dp[0][j][k]=dp[1][j][k];
            }
        }
        if(clock()-beg_time>1950000){

            for(int ff=2;ff<n+1;ff++){
                // assert(ans[i]!=inf);
                cout<<ans[ff]<<endl;
            }
            return;
        }
        
    }
    for(int i=2;i<n+1;i++){
        // assert(ans[i]!=inf);
        cout<<ans[i]<<endl;
    }

}

void testcases(int n) {
    n = 1 - n;
    if (!n) cin >> n;
    for (int i = 0; i < n; i++) {
        solve();
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    //freopen("C:\\Users\\Maximus\\CLionProjects\\Codeforces\\BestTeam\\output.txt", "r", stdin);
    //f=fopen("C:\\Users\\Maximus\\CLionProjects\\Codeforces\\BestTeam\\output.txt", "w");
    //freopen("C:\\Users\\Maximus\\CLionProjects\\Codeforces\\BestTeam\\output.txt", "w", stdout);

    testcases(0);
    // 0 - no t, 1 - with t

    unsigned int end_time = clock();
    //cout << endl << endl << end_time - beg_time;
    return 0;
}


Measured memory_bytes: 5720