#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<int(n);++i)
#define all(a) (a).begin(),(a).end()
typedef long long ll;
#define rep1(i,n) for(int i=1;i<=int(n);++i)
#define lb(s,x) (lower_bound(all(s),x)-s.begin())
#define ub(s,x) (upper_bound(all(s),x)-s.begin())
#define uniq(a) a.erase(unique(all(a)),a.end())
#define bit(k) (1LL<<(k))
const int INF = 1e9;

#define debug(x) cerr<<(#x)<<": "<<(x)<<endl
template<class T,class U>
ostream& operator<<(ostream& o, const pair<T,U> &p){
    o<<"("<<p.first<<", "<<p.second<<")";
    return o;
}
#define print(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<_<<", "; cerr<<"]"<<endl; }

// 運賃 Ai <= 50, M = 100 -> 必要最高枚数 = 10000
// dp[頂点][残り枚数] = かかった時間 

using Cost = ll; // time
struct Edge{
    Cost cost;
    int to;
    int fee;
    bool operator>(const Edge &right)const{
        return cost > right.cost;
    }
};


#define MAX_N 50
#define MAX_C 10000
ll dp[MAX_N][MAX_C+1];

int main(void){
    rep(i, MAX_N)rep(j, MAX_C+1) dp[i][j] = 1e16;
    int n, m, s;
    cin >> n >> m >> s;
    vector<vector<Edge>> g(n);
    rep(i,m) {
        ll u,v,fee,cost;
        cin >> u >> v >> fee >> cost;
        u--, v--;
        g[u].push_back((Edge){cost, (int)v, (int)fee});
        g[v].push_back((Edge){cost, (int)u, (int)fee});
    }
    rep(i,n) {
        ll c, d;
        cin >> c >> d;
        g[i].push_back((Edge){d, i, -(int)c});
    }

    dp[0][min(s,MAX_C)] = 0;
    using P = pair<Cost, pair<int, int>>;
    priority_queue<P,vector<P>,greater<P>> qu;

    qu.push({0,{0,min(s,MAX_C)}});
    while(qu.size()){
        P top = qu.top(); qu.pop();
        Cost cost = top.first;
        int cur = top.second.first;
        int rem = top.second.second;
        // debug(cost);
        // debug(cur);
        // debug(rem);

        if(dp[cur][rem] < cost) continue;
        for(Edge e : g[cur]){
            if(rem - e.fee >= 0 && dp[e.to][min(MAX_C, rem - e.fee)] > cost + e.cost) {
                dp[e.to][min(MAX_C, rem - e.fee)] = cost + e.cost;
                qu.push({cost + e.cost, {e.to, min(MAX_C, rem - e.fee)}});
            }
        }
    }
    vector<Cost> res(n, 1e18);
    rep1(i,n-1)rep(j,MAX_C+1){
        res[i] = min(res[i], dp[i][j]);
    }
    rep1(i,n-1){
        cout << res[i] << endl;
    }
    
    return 0;
}
