#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define invrepr(i,a,b) for(int i=b-1;i>=a;i--)
#define invrep(i,n) invrepr(i,0,n)
#define repitr(itr,a) for(auto itr=a.begin();itr!=a.end();++itr)
const int MOD=1e9+7;
const int INF=1e9;


int main() {
    ios_base::sync_with_stdio(false);

    int n,m,s;
    cin >> n >> m >> s;
    vector<vector<ll>> money(n,vector<ll>(n,INF)),tim(n,vector<ll>(n,INF));
    rep(i,m) {
        int u,v,a,b;
        cin >> u >> v >> a >> b;
        money[u-1][v-1]=a;
        money[v-1][u-1]=a;
        tim[u-1][v-1]=b;
        tim[v-1][u-1]=b;
    }
    vector<int> c(n),d(n);
    rep(i,n) cin >> c[i] >> d[i];
    vector<ll> cost(n,-1),mcost(n,-1);
    priority_queue<tuple<ll,int,ll>,vector<tuple<ll,int,ll>>, greater<tuple<ll,int,ll>>> pq;
    pq.push(make_tuple(0,0,s));
    int cnt=0;
    while (cnt<n) {
        tuple<ll,int,ll> now=pq.top();
        pq.pop();
        ll ti=get<0>(now);
        int pos=get<1>(now);
        ll mon=get<2>(now);
        if (mon<=mcost[pos]) continue;
        mcost[pos]=mon;
        if (cost[pos]==-1) {
            cost[pos]=ti;
            ++cnt;
        }
        rep(next,n) {
            if (tim[pos][next]!=INF && mon>=money[pos][next]) {
                pq.push(make_tuple(ti+tim[pos][next],next,mon-money[pos][next]));
            }
        }
        if (mon<2500) pq.push(make_tuple(ti+d[pos],pos,mon+c[pos]));
    }
    repr(i,1,n) cout << cost[i] << endl;

    return 0;
}