//ABC164Eより

//参考：http://ehafib.hatenablog.com/entry/2015/12/23/164517
//インクルード(アルファベット順,bits/stdc++.hは使わない派閥)
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

using namespace std;
typedef long long ll;

//マクロ
//forループ関係
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値を求める
#define MIN(x) *min_element(ALL(x)) //最小値を求める
//定数
#define INF 1000000000000000 //10^15:極めて大きい値,∞
#define MOD 10000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange(素数列挙などで使用)
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素

//ここから上はテンプレート

#define VL vector<ll>

//昇順の場合はgreater
//pairの比較は一つ目の要素二つ目の要素の優先順位
#define PQ priority_queue<VL,vector<VL>,greater<VL>>


//fは始点のインデックス
//nは頂点の総数
//edgeはそれぞれの頂点から伸びる辺についてその辺の先の頂点のインデックスおよび減る運賃および距離を持つ配列
vector<VL> dijkstra(ll f,ll n,ll s,vector<vector<VL>>& edge){
    //最短経路としてどの頂点のどの通貨の枚数の状態が確定済みかをチェックする配列
    s=min(s,ll(2999));
    vector<VL> confirm(n,VL(3000,false));
    //それぞれの頂点のそれぞれの枚数の状態への最短距離を保存する配列
    //始点の初めの状態以外はINFで最短距離を初期化する(始点はもちろん0)
    vector<VL> mincost(n,VL(3000,INF));mincost[f][s]=0;
    //確定済みの頂点の集合から伸びる辺を伝ってたどり着く頂点の始点からの距離(と枚数)を距離の短い順に保存する優先度つき配列
    PQ mincand;mincand.push({mincost[f][s],f,s});

    //mincandの要素がゼロの時、最短距離を更新できる頂点がないことを示す
    while(!mincand.empty()){
        //最短距離でたどり着くと思われる頂点を取り出す
        VL next=mincand.top();mincand.pop();
        //すでに最短距離が確定済みの場合は飛ばす
        if(confirm[next[1]][next[2]]) continue;
        //確定済みではない場合は確定済みにする
        confirm[next[1]][next[2]]=true;
        //確定済みの頂点から伸びる辺の情報をとってくる(参照の方が速い)、lはその辺の本数
        vector<VL>& v=edge[next[1]];ll l=SIZE(v);
        REP(i,l){
            //辺の先が確定済みなら更新する必要がない(次文があれば十分)
            //if(confirm[v[i].F]) continue;
            //辺の先のmincost以上の場合は更新する必要がない(辺の先が確定済みの時は満たす)
            //次の銀貨の枚数があり得るか,3000超えたらOK(3000あれば十分)
            ll nextnext=min(next[2]+v[i][1],ll(2999));
            //0より小さいと移動できない
            if(nextnext<0) continue;
            if(mincost[v[i][0]][nextnext]<=next[0]+v[i][2]) continue;
            //更新
            mincost[v[i][0]][nextnext]=next[0]+v[i][2];
            //更新した場合はその頂点が(確定済みでない頂点の中で)最短距離になる可能性があるので
            mincand.push({mincost[v[i][0]][nextnext],v[i][0],nextnext});
        }
    }
    return mincost;
}

signed main(){
    ll n,m,s;cin >> n >> m >> s;

    vector<vector<VL>> edge(n);
    REP(i,m){
        ll u,v,a,b;cin >> u >> v >> a >> b;
        edge[u-1].PB({v-1,-a,b});
        edge[v-1].PB({u-1,-a,b});
    }
    REP(i,n){
        ll c,d;cin >> c >> d;
        edge[i].PB({i,c,d});
    }
    //cout << 1 << endl;
    
    vector<VL> mincost=dijkstra(0,n,s,edge);
    //cout << 1 << endl;
    FOR(i,1,n-1) cout << MIN(mincost[i]) << endl;
}

Measured memory_bytes: 10692