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

#include<bits/stdc++.h>

class Edge{
public:
    int from, to;
    long long value, cost;
    Edge(int a, int b, long long c, long long d){
        from = a;
        to = b;
        value = c;
        cost = d;
    }
    Edge(int a,int b){
        from = a;
        to = b;
    }
};

std::vector<vector<long long>> dijkstra(int s, int N, std::vector<Edge> E, vector<long long> C, vector<long long> D, long long S){

    std::vector<vector<long long>> ans(N, vector<long long>(50 * 100 + 1, 1e18));
    std::vector<std::vector<Edge>> Edges(N);
    for(auto e : E){
        Edges.at(e.from).push_back(e);
    }
    std::priority_queue<std::pair<long long, pair<long long, int>>, std::vector<std::pair<long long, pair<long long, int>>>, std::greater<std::pair<long long, pair<long long, int>>>> que;
    ans.at(s).at(min(S, (ll)50 * 100)) = 0;
    que.push(std::make_pair(0, make_pair(min(S, (ll(50) * 100)), s)));
    while(!que.empty()){
        std::pair<long long, pair<long long, int>> p = que.top();
        que.pop();
        if(ans.at(p.second.second).at(p.second.first) < p.first)continue;
       // cout<<p.second.first<<endl;

        if(p.second.first < 50 * 100){
            long long precost = min(p.second.first + C[p.second.second], (ll)50 * 100);

            if(ans.at(p.second.second).at(p.second.first) + D[p.second.second] < ans.at(p.second.second).at(precost)){
                ans.at(p.second.second).at(precost) = ans.at(p.second.second).at(p.second.first) + D[p.second.second];
                que.push(std::make_pair(ans.at(p.second.second).at(precost), make_pair(precost , p.second.second)));
            }
        }
        for(int i = 0;i < Edges.at(p.second.second).size();i++){
            if(p.second.first >= Edges.at(p.second.second).at(i).cost){
                if(ans.at(p.second.second).at(p.second.first) + Edges.at(p.second.second).at(i).value < ans.at(Edges.at(p.second.second).at(i).to).at(p.second.first - Edges.at(p.second.second).at(i).cost)){
                    ans.at(Edges.at(p.second.second).at(i).to).at(p.second.first - Edges.at(p.second.second).at(i).cost) = ans.at(p.second.second).at(p.second.first) + Edges.at(p.second.second).at(i).value;
                    que.push(std::make_pair(ans.at(Edges.at(p.second.second).at(i).to).at(p.second.first - Edges.at(p.second.second).at(i).cost), make_pair(p.second.first - Edges.at(p.second.second).at(i).cost, Edges.at(p.second.second).at(i).to)));
                }
            }
        }
    }
    /*
    for(int i = 0;i < N;i++){
        for(int j = 0;j < 20;j++){
            cout<<ans[i][j]<<" ";
        }
        cout<<endl;
    }
    */
    return ans;
}


void solve(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){
    vector<Edge> Edges;
    for(int i = 0;i < M;i++){
        U[i]--, V[i]--;
        Edges.push_back(Edge(U[i], V[i], B[i], A[i]));
        Edges.push_back(Edge(V[i], U[i], B[i], A[i]));
    }
    vector<vector<long long>> d = dijkstra(0, N, Edges, C, D, S);
    for(int i = 1;i < N;i++){
        cout<<*min_element(d[i].begin(), d[i].end())<<endl;;
    }
}

int main(){
    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]);
        scanf("%lld",&A[i]);
        scanf("%lld",&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]);
    }
    solve(N, M, S, std::move(U), std::move(V), std::move(A), std::move(B), std::move(C), std::move(D));
    return 0;
}


Measured memory_bytes: 11504