/*
これを入れて実行
g++ code.cpp
./a.out
 */
 
#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <math.h>
#include <tuple>
#include <iomanip>
#include <bitset>
#include <functional>

#define all(x) (x).begin(),(x).end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
using namespace std;
typedef long long ll;
typedef long double ld;
 
int dy4[4] = {-1, 0, +1, 0};
int dx4[4] = {0, +1, 0, -1};
int dy8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dx8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
 
const long long INF = 1LL << 62;
const ll MOD = 1e9 + 7;
 
bool greaterSecond(const pair<int, int>& f, const pair<int, int>& s){
    return f.second > s.second;
}
 
ll gcd(ll a, ll b){
	if (b == 0)return a;
	return gcd(b, a % b);
}
 
ll lcm(ll a, ll b){
    return a / gcd(a, b) * b;
}

ll conbinationMemo[100][100];

ll cmemoInit(){
    rep(i, 100){
        rep(j, 100){
            conbinationMemo[i][j] = -1;
        }
    }
}
 
ll nCr(ll n, ll r){
    if(conbinationMemo[n][r] != -1) return conbinationMemo[n][r];
    if(r == 0 || r == n){
        return 1;
    } else if(r == 1){
        return n;
    }
    return conbinationMemo[n][r] = (nCr(n - 1, r) + nCr(n - 1, r - 1));
}
 
ll nPr(ll n, ll r){
    r = n - r;
    ll ret = 1;
    for (ll i = n; i >= r + 1; i--) ret *= i;
    return ret;
}
 
//-----------------------ここから-----------
struct Obj{
    ll to;
    ll cost;
    ll time;
};
ll dp[55][5500] = {0};
int main(void){
    ll n, m, s;
    cin >> n >> m >> s;
    vector<vector<Obj>> g(n);
 
    rep(i, m){
        ll u, v, a, b;
        cin >> u >> v >> a >> b;
        u--, v--;
        Obj tmp;
        tmp.to = v;
        tmp.cost = a;
        tmp.time = b;
        g[u].push_back(tmp);
        tmp.to = u;
        g[v].push_back(tmp);
    }
 
    vector<pair<ll,ll>> trade(n);
    rep(i, n){
        ll c, d;
        cin >> c >> d;
        trade[i] = {c, d};
    }
 
    s = min(s, 5400LL);
 
    rep(i, 55){
        rep(j, 5500){
            dp[i][j] = INF;
        }
    }
 
    dp[0][s] = 0;
 
    queue<pair<pair<ll,ll>, ll>> q;
    q.push({{0, 0}, s});
 
    while(!q.empty()){
        ll now = q.front().first.second;
        ll nowtime = q.front().first.first;
        ll nowsilver = q.front().second;
        q.pop();
        //cout << now << " " << nowsilver << " " << dp[now][nowsilver] << endl;
        if(dp[now][nowsilver] < nowtime) continue;

        if(nowsilver + trade[now].first < 5400){
            ll nexttime = nowtime + trade[now].second;
            ll nextlsilver = nowsilver + trade[now].first;
            if(dp[now][nextlsilver] > nexttime){
                dp[now][nextlsilver] = nexttime;
                q.push({{nexttime, now}, nextlsilver});
            }
        }

        rep(i, g[now].size()){
            Obj nextobj = g[now][i];
            ll nexttime = nowtime + nextobj.time;
            if(nowsilver < nextobj.cost) continue;
            ll nextsilver = nowsilver - nextobj.cost;
            if(dp[nextobj.to][nextsilver] <= nexttime) continue;
            dp[nextobj.to][nextsilver] = nexttime;
            q.push({{nexttime, nextobj.to}, nextsilver});
        }
    }
 
    for(int i = 1; i < n; i++){
        ll ans = INF;
        for(int j = 0; j < 5400; j++){
            //cout << i << " " << j << " " << dp[i][j] << endl;
            ans = min(ans, dp[i][j]);
        }
        cout << ans << endl;
    }
}


Measured memory_bytes: 8448