#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ll mod = 1e9 + 7;
//const ll mod = 998244353;
#define REP(i,n) for(int i=0;i<(int)n;++i)
//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << 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 (a>b) { a=b; return 1; } return 0; }
template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}
string num2bit(ll num, ll len){
    string bit = "";
    REP(i, len){
    bit += char('0'+(num>>i & 1));
    }
    return bit;
}

struct Edge{
    ll dst;
    ll weight;
    Edge(ll dst, ll weight): dst(dst), weight(weight) {}
};

struct TmpDist{
    ll vertex;
    ll dist;
    TmpDist(ll vertex, ll dist): vertex(vertex), dist(dist) {}
    bool operator< (const TmpDist& right)const{
        return dist > right.dist;
    }
};

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
const ll INFLL = LLONG_MAX/3;

vector<ll> dijkstra(Graph &G, ll r){
    ll V = G.size();
    vector<ll> dist(V, INFLL);
    priority_queue<TmpDist> pq;
    vector<bool> check(V, false);
    TmpDist init(r, 0);
    pq.push(init);
    while(!pq.empty()){
        TmpDist td = pq.top();pq.pop();
        ll now = td.vertex;
        if(!check[now]){
            check[now] = true;
            dist[now] = td.dist;
            for (int i=0;i<(int)G[now].size();i++){
                if(dist[G[now][i].dst] > td.dist + G[now][i].weight){
                    TmpDist tdCandidate(G[now][i].dst, td.dist + G[now][i].weight);
                    pq.push(tdCandidate);
                }
            }
        }
    }
    return dist;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll N, M, S;
    cin >> N >> M >> S;

    vector<ll> u(M), v(M), A(M), B(M);
    REP(i, M) cin >> u[i] >> v[i] >> A[i] >> B[i];
    REP(i, M) u[i]--, v[i]--;

    vector<ll> C(N), D(N);
    REP(i, N) cin >> C[i] >> D[i];

    ll MA = 6010;
    Graph G(MA*N);

    REP(idx, M){
        REP(i, MA){
            ll from = MA * u[idx] + i;
            ll to = MA * v[idx] + i-A[idx];
            ll w = B[idx];
            if(i>=A[idx]){
                G[from].push_back({to, w});
            }

            from = MA * v[idx] + i;
            to = MA * u[idx] + i-A[idx];
            w = B[idx];
            if(i>=A[idx]){
                G[from].push_back({to, w});
            }
        }
    }

    REP(v, N){
        REP(i, MA){
            ll from = MA * v + i;
            ll to = MA * v + i+C[v];
            ll w = D[v];
            if(i+C[v]<MA){
                G[from].push_back({to, w});
            }
        }
    }

    ll start = 0*MA + min(MA-1, S);
    auto dist = dijkstra(G, start);

    REP(i, N){
        if(i==0) continue;
        ll res = INFLL;
        REP(j, MA){
            chmin(res, dist[MA*i+j]);
        }
        cout << res << endl;
    }

    return 0;
}

Measured memory_bytes: 56076