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

#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define NUM 2520
#define INF (1LL<<50)
#define DEBUG 0
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())
#define PI (3.141592653589794)
#define TO_STRING(VariableName) # VariableName
#define LOG(x) if(DEBUG)cout<<TO_STRING(x)<<"="<<x<<" "<<endl;
#define LOG2(x,y) if(DEBUG)cout<<TO_STRING(x)<<"="<<x<<" "<<TO_STRING(y)<<"="<<y<<endl;
#define LOG3(x,y,z) if(DEBUG)cout<<TO_STRING(x)<<"="<<x<<" "<<TO_STRING(y)<<"="<<y<<" "<<TO_STRING(z)<<"="<<z<<endl;
#define LOG4(w,x,y,z) if(DEBUG)cout<<TO_STRING(w)<<"="<<w<<" "<<TO_STRING(x)<<"="<<x<<" "<<TO_STRING(y)<<"="<<y<<" "<<TO_STRING(z)<<"="<<z<<endl;

template<class T>bool chmax(T & a, const T & b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }

using pll = pair<lli,pair<lli,lli> >; //time to money

#define MAX_V 1000000
struct edge{
    lli to;
    lli cost;
};
bool operator< (const edge &l, const edge &r){
    return l.cost < r.cost;
}
bool operator> (const edge &l, const edge &r){
    return l.cost > r.cost;
}
vector<pll> G[MAX_V];

void func(long long N, long long M, long long S, std::vector<long long> U, std::vector<long long> V, std::vector<long long> A, std::vector<long long> B, std::vector<long long> C, std::vector<long long> D){
    
    const int MAX = 2500;
    priority_queue<pll,vector<pll>,greater<pll>> que;
    vector<vector<lli>> d(N+2,vector<lli>(MAX+1,INF));
    //fill(d,d+n+2,INF);
    if(S>=MAX)S=MAX;
    d[0][S]=0;
    que.push({0,{0,S}});

    while(!que.empty())
    {
        auto p = que.top();
        lli to = p.second.first;
        lli time = p.first;
        lli money = p.second.second;
        que.pop();

        if(time > d[to][money])continue;
        
        if(money + C[to] <= MAX){
            lli nextMoney = money + C[to];
            lli nextTime  = time  + D[to];
            if(chmin(d[to][nextMoney],nextTime)){
                que.push({nextTime,{to,nextMoney}});
            }
        }
        for(auto e:G[to]){
            if(money < e.second.first)continue;

            lli nextTo = e.first;
            lli nextMoney = money - e.second.first;
            lli nextTime = time + e.second.second;
            if(chmin(d[nextTo][nextMoney],nextTime)){
                que.push({nextTime,{nextTo,nextMoney}});
            }
        }
    }
    REP(i,1,N){
        lli res = INF;
        REP(s,0,MAX+1)chmin(res,d[i][s]);
        cout<<res<<endl;
    }
}

int main(){
    // cout << fixed << setprecision(5);

    long long N;
    scanf("%lld",&N);
    long long M;
    scanf("%lld",&M);
    long long S;
    scanf("%lld",&S);
    std::vector<long long> U(M);
    std::vector<long long> V(M);
    std::vector<long long> A(M);
    std::vector<long long> B(M);
    for(int i = 0 ; i < M ; i++){
        scanf("%lld",&U[i]);
        scanf("%lld",&V[i]);
        U[i]--,V[i]--;
        scanf("%lld",&A[i]);
        scanf("%lld",&B[i]);
        G[U[i]].push_back({V[i],{A[i],B[i]}});
        G[V[i]].push_back({U[i],{A[i],B[i]}});
    }
    std::vector<long long> C(N);
    std::vector<long long> D(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&C[i]);
        scanf("%lld",&D[i]);
    }
    func(N, M, S, std::move(U), std::move(V), std::move(A), std::move(B), std::move(C), std::move(D));
    return 0;
}
