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

#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define MIN(a) *min_element(all(a))
#define MAX(a) *max_element(all(a))
#define SUM(a) accumulate(all(a), 0LL)
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define RREP(i, n) for(int (i)=(n)-1; (i)>=0; (i)--)
#define FOR(i, m, n) for(int (i)=(m); (i)<(n); i++)
#define FORR(i, m, n) for(int (i)=(n)-1; (i)>=(m); i--)
#define debug(x) cerr << #x << " = " << x << endl
//#define int long long

typedef long long ll;
//ll const MOD = 998244353;
ll const MOD = 1e9+7;
int const inf = 1e9;
ll const INF = 1e18;

inline void ios_(){cin.tie(0); ios::sync_with_stdio(false);}
template<typename T> int size(const T& a){return (int)a.size();}
template<typename T> T Div(T a, T b){return (a + b - 1) / b;}
template<typename T> bool chmin(T& a, const T& b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, const T& b){if(a < b){a = b; return true;} return false;}

//Graph in adjcency list
struct Graph{
    struct Edge{
        int from;
        int to;
        ll time;
        Edge(int a, int b, ll t) : from(a), to(b), time(t) {}
    };

    int N;  //頂点数
    vector<vector<Edge>> edges;   //隣接リスト
    vector<ll> dist;   //ノードの深さ
    vector<vector<ll>> cost, time;
    ll sc;
    ll maxc;

    Graph(int n, int m, ll sc) : N(n), maxc(m), edges(n), dist(n*m, INF),
    cost(n, vector<ll>(n, INF)), time(cost), sc(sc) {}

    void connect(int a, int b, ll c){   //辺を追加
        edges[a].emplace_back(Edge(a, b, c));
    }

    void resetDist(){
        for(int i=0; i<N; i++){
            dist[i] = INF;
        }
    }

    void dijkstra(int start){   //ダイクストラ法
        start = start*maxc + sc;
        // dist[start] = 0;

        auto fn = [](const Edge& a, const Edge& b){return a.time > b.time;};
        priority_queue<Edge, vector<Edge>, decltype(fn)> que(fn);

        int cnt = 0;

        que.push(Edge(start, start, 0));

        while(!que.empty() && cnt < N){
            auto e = que.top();
            que.pop();
            int v = e.to / maxc;
            ll c = e.to % maxc;

            if(!chmin(dist[e.to], e.time)){
                continue;
            }

            for(const auto& i : edges[v]){
                int u = i.to;
                ll d = min(maxc - 1, c - cost[v][u]);
                if(d < 0 || dist[u*maxc + d] < INF) continue;
                que.push(Edge(e.to, u*maxc + d, e.time + time[v][u]));
            }
        }
    }
};


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

    ll maxc = 2600;

    Graph G(n, maxc, min(s, maxc - 1));

    REP(i, n){
        G.connect(i, i, 1);
    }

    REP(i, m){
        int u, v;
        ll a, b;
        cin >> u >> v >> a >> b;
        u--;
        v--;
        G.connect(u, v, 1);
        G.connect(v, u, 1);
        G.cost[u][v] = a;
        G.cost[v][u] = a;
        G.time[u][v] = b;
        G.time[v][u] = b;
    }

    REP(i, n){
        ll a, b;
        cin >> a >> b;
        G.cost[i][i] = -a;
        G.time[i][i] = b;
    }

    G.dijkstra(0);
    FOR(i, 1, n){
        cout << *min_element(G.dist.begin() + i*maxc, G.dist.begin() + (i+1)*maxc) << endl;
    }

    return 0;
}


Measured memory_bytes: 8412