#include<bits/stdc++.h>

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;++A)
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

/////////////////////////////////////////////////////

ll N,M,S;
ll C[111],D[111];
vector<pair<ll,pll>> uvv[1111];

ll i, j, k;

void query(ll aa){
    ll i,j,k;
    priority_queue<pair<ll,pll>> q;
    vector<vector<bool>> mk(N + 5, vector<bool>(5555));
    q.push({0, {1, S > 5000 ? 5000 : S}});
    while(q.size()){
        ll d = q.top().first;
        pll qa = q.top().second;
        q.pop();
        ll a = qa.first;
        ll c = qa.second;
        if(a==aa){
            printf("%lld\n", -d);
            return;
        }
        if(mk[a][c])
            continue;
        mk[a][c] = true;
        if(c<5000){
            q.push({d - D[a], {a, min(5000ll, c + C[a])}});
        }
        fornum(i,0,uvv[a].size()){
            auto bbb = uvv[a][i];
            ll bb = bbb.first;
            ll cc = bbb.second.first;
            ll dd = bbb.second.second;
            if(c<cc)
                continue;
            if(mk[bb][c-cc])
                continue;
            q.push({d - dd, {bb, c - cc}});
        }
    }
}

int main(){
    scanf("%lld%lld%lld", &N, &M, &S);
    fornum(i,0,M){
        ll u, v, a, b;
        scanf("%lld%lld%lld%lld", &u, &v, &a, &b);
        uvv[u].push_back({v, {a, b}});
        uvv[v].push_back({u, {a, b}});
    }
    fornum(i,0,N){
        scanf("%lld%lld", &C[i+1], &D[i+1]);
    }

    fornum(i,1,N){
        query(i + 1);
    }
    return 0;
}