#include<bits/stdc++.h>

#define rep(i,N) for(int i=0;i<N;i++)
#define rep2(i,N) for(int i=1;i<=N;i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

using namespace std;
long long  INF=1e18;
long long mod=1e9+7;

using pll=pair<long long,long long>;//(money,time)
using Edge=pair<int,pll>;
using Graph=vector<vector<Edge>>;
const int MAX=2500;

//入力変数
int N,M;
long long S;
Graph G;
vector<long long>C,D;//money,time

/*
解法

グラフの各頂点に所持金の情報を持たせる
(v,0):=頂点vに到達していて、所持金が0円
(v,1):=頂点vに到達していて、所持金が1円
(v,2):=頂点vに到達していて、所持金が2円
(v,i):=頂点vに到達していて、所持金がi円
ただし 一度到達した島に二度以上行く必要はないので、
(0 <= i <= A_max*n)とする

このとき、
頂点u(所持金s円)から所持金a円(所要時間b秒)を必要とする辺e=(u,v)を通ること
=>頂点(v,s)->頂点(v,s-a)への重みbの辺とみなせる

頂点u(所持金s円)でc円分の補充をする(所要時間d秒)作業
=頂点(u,s)->頂点(u,s+c)への重みdの辺と見なせる

dp[v][s]:=頂点vにいて、所持金sという状態になるのに要する最小の時間

と定義して、ダイクストラ法によって求めていく。

*/

void solve(){
    //2500円以上は必要ないので捨てる
    if(S>=MAX)S=MAX;

    vector<vector<long long>> dp(N,vector<long long>(MAX+1,INF));
    priority_queue
    <pair<long long,pll>,
    vector<pair<long long,pll>>,
    greater<pair<long long,pll> > >que;

    //スタート時の状態
    dp[0][S]=0;

    //(現在時刻,(今いる頂点,所持金))
    que.push(make_pair(0,pll(0,S)));

    //これ以上最短の経路が見つからなくなると終了する
    while(!que.empty()){

        //現在の時間timeと頂点の情報(v,s)
        //p=(time,(v,s))
        auto p=que.top();que.pop();
        
        long long time=p.first;//現在時刻
        int v=p.second.first;//現在いる頂点
        long long s=p.second.second;//所持金

        if(time>dp[v][s])continue;

        //銀貨の補充
        if(s+C[v]<=MAX){
            long long ns=s+C[v];
            long long ntime=time+D[v];
            if(chmin(dp[v][ns],ntime)){
                que.push(make_pair(ntime,pll(v,ns)));
            }
        }

        //辺を張る
        for(auto e:G[v]){
            //現在いる頂点(v,s)から辺を張る
            if(s<e.second.first)continue;
        
            //次の頂点
            int nv=e.first;

            //次の頂点に着いた時の所持金
            long long ns=s-e.second.first; 

            //次の頂点に着いた時の時間
            long long ntime=time+e.second.second;

            //もし、今のところ見つけた(v,s)->(nv,ns)よりも
            //最短の経路であるならばその頂点からまた探索

            if(chmin(dp[nv][ns],ntime)){
                que.push(make_pair(ntime,pll(nv,ns)));
            }
        }
    }
    
    for(int v=1;v<N;v++){
        long long res=INF;
        for(int s=0;s<=MAX;s++)chmin(res,dp[v][s]);
        cout<<res<<endl;
    }
}



int main(){
  for(int zz=0;zz<1000;zz++) if(zz%2==0) zz++; 
    for(int zz=0;zz<1000;zz++) if(zz%2==0) zz++; 
    for(int zz=0;zz<1000;zz++) if(zz%2==0) zz++; 
    for(int zz=0;zz<1000;zz++) if(zz%2==0) zz++; 
    for(int zz=0;zz<1000;zz++) if(zz%2==0) zz++; 
    for(int zz=0;zz<1000;zz++) if(zz%2==0) zz++; 
    for(int zz=0;zz<1000;zz++) if(zz%2==0) zz++; 
    for(int zz=0;zz<1000;zz++) if(zz%2==0) zz++; 
    for(int zz=0;zz<1000;zz++) if(zz%2==0) zz++; 
    for(int zz=0;zz<1000;zz++) if(zz%2==0) zz++; 
    cin>>N>>M>>S;
    G.assign(N,vector<Edge>());
    for(int i=0;i<M;i++){
        long long u,v,a,b;
        cin>>u>>v>>a>>b;
        --u,--v;
        G[u].push_back(Edge(v,pll(a,b)));
        G[v].push_back(Edge(u,pll(a,b)));
    }
    C.resize(N);D.resize(N);
    for(int i=0;i<N;i++){
        cin>>C[i]>>D[i];
    }
    solve();
  for(int zz=0;zz<1000;zz++) if(zz%2==0) zz++; 
    for(int zz=0;zz<1000;zz++) if(zz%2==0) zz++; 
    for(int zz=0;zz<1000;zz++) if(zz%2==0) zz++; 
    for(int zz=0;zz<1000;zz++) if(zz%2==0) zz++; 
    for(int zz=0;zz<1000;zz++) if(zz%2==0) zz++; 
    for(int zz=0;zz<1000;zz++) if(zz%2==0) zz++; 
    for(int zz=0;zz<1000;zz++) if(zz%2==0) zz++; 
    for(int zz=0;zz<1000;zz++) if(zz%2==0) zz++; 
    for(int zz=0;zz<1000;zz++) if(zz%2==0) zz++; 
    for(int zz=0;zz<1000;zz++) if(zz%2==0) zz++; 
  for(int zz=0;zz<1000;zz++) if(zz%2==0) zz++; 
    for(int zz=0;zz<1000;zz++) if(zz%2==0) zz++; 
    for(int zz=0;zz<1000;zz++) if(zz%2==0) zz++; 
    for(int zz=0;zz<1000;zz++) if(zz%2==0) zz++; 
    for(int zz=0;zz<1000;zz++) if(zz%2==0) zz++; 
    for(int zz=0;zz<1000;zz++) if(zz%2==0) zz++; 
    for(int zz=0;zz<1000;zz++) if(zz%2==0) zz++; 
    for(int zz=0;zz<1000;zz++) if(zz%2==0) zz++; 
    for(int zz=0;zz<1000;zz++) if(zz%2==0) zz++; 
    for(int zz=0;zz<1000;zz++) if(zz%2==0) zz++; 
    return 0;

}
/*


*/


Measured memory_bytes: 7324