#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <sstream>
#include <string>
#define _repargs(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _repargs(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define mp make_pair
#define pb push_back
typedef long long ll;
using namespace std;
template <typename T>
inline void output(T a, int p = 0) {
    if(p) cout << fixed << setprecision(p)  << a << "\n";
    else cout << a << "\n";
}
// end of template

const ll inf = 1LL << 62;
//struct edge {int to; ll cost;};
struct edge {int to; ll cost;};
struct node {int pos; ll cost;};
bool operator < (const node &a, const node &b){
    return a.cost > b.cost;
}

const int d = 2501;
int N;
vector<ll> dijkstra(vector<vector<edge>> &G, int root, int S){
    vector<ll> ret(G.size(), inf);
    priority_queue<node> pq;
    pq.push({root + N * S, 0});
    while (!pq.empty()) {
        node t = pq.top();
        pq.pop();
        
        if (ret[t.pos] == inf) ret[t.pos] = t.cost;
        else continue;
        
        for (edge e : G[t.pos]) {
            pq.push({e.to, t.cost + e.cost});
        }
    }
    return ret;
}



int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    // source code
    int M;
    ll S;
    cin >> N >> M >> S;
    vector<vector<edge>> G(N * d);
    rep(i, M) {
        int U, V;
        int A;
        ll B;
        cin >> U >> V >> A >> B;
        U--;
        V--;
        rep(i, d) {
            if(i - A >= 0) G[U + N * i].pb({V + N * (i - A), B});
            if(i - A >= 0) G[V + N * i].pb({U + N * (i - A), B});
        }
    }
    rep(i, N) {
        ll C, D;
        cin >> C >> D;
        rep(j, d - 1) {
            G[i + N * j].pb({i + N * (int)min(ll(d) - 1, C + j), D});
        }
    }
    
    vector<ll> ans = dijkstra(G, 0, (int)min((ll)d - 1, S));
    
    vector<ll> ret(N, inf);
    rep(i, N) {
        rep(j, d) {
            ret[i] = min(ret[i], ans[i + j * N]);
        }
    }
    
    rep(i, 1, N) output(ret[i]);
    
    
    
    
    return 0;
}
