#include <bits/stdc++.h>
#include <stdlib.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> P;
typedef priority_queue<P,vector<P>,greater<P>> P_queue;

#define REP(i,a,b) for(int i=(int)a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define mp make_pair
#define ALL(a) a.begin(),a.end()
#define SORT(a) sort(ALL(a))
#define U_ERASE(V) V.erase(unique(ALL(V)), V.end());

const ll MOD=998244353;
const ll mod=1000000007;
const ll INF=1e15;
vec dx={1,0,-1,0};
vec dy={0,1,0,-1};

ll dp[51][5001];
ll Kokan[51][2];
ll Nedan[102];
ll Jikan[102];
vector<P> d[51];
int main(){
    ll N,M,S; cin>>N>>M>>S;
    rep(i,51) rep(j,5001) dp[i][j]=INF;
    if(S>=5000) S=5000;
    rep(i,M){
        ll U,V,A,B; cin>>U>>V>>A>>B;
        U--; V--;
        d[U].pb(mp(V,i));
        d[V].pb(mp(U,i));
        Nedan[i]=A;
        Jikan[i]=B;
    }
    rep(i,N) cin>>Kokan[i][0]>>Kokan[i][1];
    dp[0][S]=0;
    P_queue Q;
    Q.push(mp(0,S));
    vec ans(N,INF);
    ll count=0;
    while(!Q.empty()){
        ll A=Q.top().first, P=Q.top().second/10000, Money=Q.top().second%10000;
        //cout<<A<<' '<<P<<' '<<Money<<endl;
        if(ans[P]>A) {ans[P]=A; count++;}
        if(count==N) break;
        Q.pop();
        ll x=Money+Kokan[P][0];
        if(x>=5000) x=5000;
        if(Money!=5000) if(A+Kokan[P][1]<dp[P][x]) {dp[P][x]=A+Kokan[P][1]; Q.push(mp(A+Kokan[P][1],P*10000+x));}
        rep(i,d[P].size()){
            ll saki=d[P][i].first, Ned=Nedan[d[P][i].second], Jik=Jikan[d[P][i].second];
            if(Money-Ned>=0) if(A+Jik<dp[saki][Money-Ned]) {dp[saki][Money-Ned]=A+Jik; Q.push(mp(A+Jik,saki*10000+(Money-Ned)));}
        }
        
    }
    REP(i,1,N) cout<<ans[i]<<endl;

}