#include <bits/stdc++.h>
#include <regex>
#ifdef _DEBUG
#include "debug.h"
#endif
#define int ll
#define float double
#define FOR(i, s, e) for (int i = int(s); i < int(e); ++i)
#define REP(i, e) FOR(i, 0, e)
#define all(v) (v).begin(),(v).end()
#define mkpr make_pair
#define mktp make_tuple
#define tv(tp, i) get<(i)>(tp)
#define CLEAR(obj) obj = decltype(obj)()
#define var auto
#define OUT(type) type &
#define IN(type) const type &
#define self (*this)
#define in :
#define True true
#define False false
using namespace std; using int32 = int32_t; using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>; using vl = vector<ll>; using vvl = vector<vl>;
using vb = vector<bool>; using vvb = vector<vb>; using vc = vector<char>; using vvc = vector<vc>;
using vf = vector<float>; using vvf = vector<vf>; using vd = vector<double>; using vvd = vector<vd>;
using str = string; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>; using pff = pair<float, float>; using pdd = pair<double, double>;
using psl = pair<string, ll>; using tiii = tuple<int, int, int>; using tlll = tuple<ll, ll, ll>;
static const int MGN = 10; static const int ARYSZ_MAX = (int)1e7; static const ll LINF = LLONG_MAX/2;
#ifdef int
static const int INF = LINF;
#else
static const int INF = INT_MAX/2;
#endif
static double EPS = 1e-9;
#define FASTCIN() cin.tie(0);ios::sync_with_stdio(false);
#ifdef IMPORT_SAMPLE
#define DEBUG_IMPORT(file) vs args(argv, argv+argc);str sample = make_sample(args, file);ifstream ifs(sample); cin.rdbuf(ifs.rdbuf());
#else
#define DEBUG_IMPORT(file)
#endif
static inline int ord(char c) {return (int)c;}
static inline char chr(int n) {return (char)n;}
static inline bool DBLEQ(double a, double b) {return abs(a - b) < EPS;}
static inline void EPR(str msg) {cerr << msg << endl;}
static inline void AST(bool exp, str msg) {if(!exp){EPR(msg);} assert(exp);}
static inline void TAST(bool exp, str msg) {if(!exp){EPR(msg);} while(!exp){}}

template <typename T>
using priority_queue_min = priority_queue<T, vector<T>, greater<T>>;

void dijkstra(OUT(vvi) tm, IN(vector<vector<tiii>>) egs, int start, int money, int MMAX){
    int N = egs.size();
    money = min(money, MMAX);
    tm = vvi(N, vi(MMAX + 4, INF));
    tm[start][money] = 0;
    var pq = priority_queue_min<tiii>();
    pq.push(mktp(tm[start][money], start, money));
    while (not pq.empty()) {
        var tp = pq.top(); pq.pop();
        int t = tv(tp, 0);
        int x = tv(tp, 1);
        int s = tv(tp, 2);
        for (var eg : egs[x]) {
            int nx = tv(eg, 0);
            int nt = t + tv(eg, 1);
            int ns = min(s - tv(eg, 2), MMAX);
            if (ns < 0)
                continue;
            if (nt < tm[nx][ns]) {
                tm[nx][ns] = nt;
                pq.push(mktp(nt, nx, ns));
            }
        }
    }
}


int32 main(int32 argc, char* argv[]) {
    FASTCIN();
    DEBUG_IMPORT("sample-4");


    int N,M,S; cin>>N>>M>>S;
    vi U(M),V(M),A(M),B(M);
    int AMAX = 0;
    REP(i,M) {
        cin>>U[i]>>V[i]>>A[i]>>B[i];
        U[i]-=1;V[i]-=1;
        AMAX = max(AMAX, A[i]);
    }
    vi C(N), D(N);
    REP(i,N) cin>>C[i]>>D[i];

    var egs = vector<vector<tiii>>(N);
    REP(i,M) {
        egs[U[i]].emplace_back(mktp(V[i], B[i], A[i]));
        egs[V[i]].emplace_back(mktp(U[i], B[i], A[i]));
    }
    REP(i,N)
        egs[i].emplace_back(mktp(i, D[i], -C[i]));


    vvi tm;
    int MMAX = AMAX*(N-1);
    dijkstra(tm, egs, 0, S, MMAX);

    vi ans(N, INF);
    REP(i,N)
        REP(j, MMAX+1)
            ans[i] = min(ans[i], tm[i][j]);

    FOR(i,1,N)
        cout << ans[i] << endl;


    return 0;
}


Measured memory_bytes: 7236