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

const ll maxs = 1e5+5;
const ll lmaxs = 20;
ll mod = 1e9+7;
ll oo = 1e15;

#define IOS ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define I insert
#define endl '\n'

void pre(){
    
}

#define tlll tuple<ll,ll,ll>
#define mt make_tuple
vector<ll> graph[55];
pair<ll,ll> A[55][55];
pair<ll,ll> C[55];
ll dp[55][2505];
ll n,m,S;

void solve(){
    
    cin >> n >> m >> S;

    for(ll i=0;i<n+1;i++){
        for(ll j=0;j<n+1;j++){
            A[i][j] = {-1,-1};
        }
    }

    for(ll i=0;i<m;i++){
        ll x,y;
        cin >> x >> y;
        x--;y--;
        graph[x].pb(y);
        graph[y].pb(x);
        ll a,b;
        cin >> a >> b;
        A[x][y] = {a,b};
        A[y][x] = {a,b};
    }
    for(ll i=0;i<n;i++){
        cin >> C[i].ff >> C[i].ss;
    }

    for(ll i=0;i<55;i++){
        for(ll j=0;j<2505;j++){
            dp[i][j] = oo;
        }
    }
    dp[0][S] = 0;

    priority_queue<tlll,vector<tlll>,greater<tlll> > pq;
    /*
        0 : time
        1 : node
        2 : coins  
    */
    pq.push(mt(0,0,S));
    while (pq.size()){
        tlll curr = pq.top();
        pq.pop();

        ll time_s = get<0>(curr);
        ll s = get<1>(curr);
        ll coins = get<2>(curr);

        if( dp[s][coins] + C[s].ss <  dp[s][min(2500ll,coins + C[s].ff)] ){
            dp[s][min(2500ll,coins + C[s].ff)] =  dp[s][coins] + C[s].ss;
            pq.push(mt(dp[s][coins] + C[s].ss,s,min(2500ll,coins + C[s].ff)));
        }

        for(auto child : graph[s]){
            ll rem_coins = coins - A[s][child].ff;
            if( rem_coins < 0 ) 
                continue;
            ll time_child = time_s + A[s][child].ss;
            if( dp[child][rem_coins] > time_child ){
                dp[child][rem_coins] = time_child;
                pq.push(mt(time_child,child,rem_coins));
            }
        }
    }

    for(ll i=1;i<n;i++){
        ll ans=oo;
        for(ll j=0;j<2501;j++){
            ans = min(ans , dp[i][j]);
        }
        cout << ans << endl; 
    }

}

int main(){
    IOS;
    pre();
    ll T = 1;
    //cin>>T;
    while(T--){
        solve();   
    }
    return 0;
}