#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 piil pair<pair<int, int>, ll>
#define plii pair<pair<ll, 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>>

const int mxn=2501;

void link(int u, int v, int cost, int w, vector<vector<vector<piii>>> &vert){
    for(int i=0;i<mxn;i++){
        if(cost+i<0) continue;
        vert[u][i].pb({{v,min(cost+i, mxn-1)}, w});
        //cout<<"from "<<u<<" "<<i<<" to "<<v<<" "<<min(cost+i, mxn-1)<<" for cost "<<w<<endl;
    }
}

vector<vector<ll>> dijekstra(vector<vector<vector<piii>>> &vert, int n, int s){
    ll inf =1e18;
    vector<vector<bool>> was(n+1, vector<bool>(mxn, false));
    vector<vector<ll>> dist(n+1, vector<ll>(mxn, inf));
    dist[1][s]=0;
    set<plii> setik;
    setik.insert({{0, 1}, s});
    while(!setik.empty()){
        plii now=*setik.begin();
        was[now.first.second][now.second]=true;
        setik.erase(setik.begin());
        for(auto & g:vert[now.first.second][now.second]){
            if(was[g.first.first][g.first.second]) continue;
            setik.erase({{dist[g.first.first][g.first.second], g.first.first}, g.first.second});
            dist[g.first.first][g.first.second]=min(dist[g.first.first][g.first.second], dist[now.first.second][now.second]+g.second);
            setik.insert({{dist[g.first.first][g.first.second], g.first.first}, g.first.second});
        }
    }
    return dist;
}
void solve() {
    int n, m ,s;
    cin>>n>>m>>s;
    vector<vector<vector<piii>>> vert(n+1 , vector<vector<piii>>(mxn));
    for(int i=0;i<m;i++){
        int u,v,a,b;
        cin>>u>>v>>a>>b;
        link(u, v, -a, b, vert);
        link(v, u, -a, b, vert);
    }
    for(int i=1;i<n+1;i++){
        int c,d;
        cin>>c>>d;
        link(i,i,c,d, vert);
    }
    vector<vector<ll>> dist=dijekstra(vert, n, min(mxn-1, s));

    for(int i=2;i<n+1;i++){
        ll ans=1e18;
        for(int j=0;j<mxn;j++){
            ans=min(ans, dist[i][j]);
        }
        cout<<ans<<" ";
    }
}

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);

    unsigned int beg_time = clock();
    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: 21952