#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long ll;
typedef pair<ll,ll> P;
const ll mod=1000000007;
const ll LINF=1LL<<60;
const int INF=1<<30;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

ll n,m,S;
vector<vector<pair<int,P>>> G;
vector<ll> C,D;

void solve(){
	S = min(S,2500LL);
	vector<vector<ll>> dp(n,vector<ll>(3000,LINF));//dp[i][s] = 0からiに銀貨をs枚持って行くときかかる時間の最小値
	priority_queue<pair<ll,P>, vector<pair<ll,P>>,greater<pair<ll,P>> > q;
	dp[0][S] = 0;
	q.push(mp(0,mp(0,S)));
	while(!q.empty()){
		auto p = q.top();q.pop();
		ll time = p.fs;
		int v = p.sc.fs;
		ll s = p.sc.sc;
		if (time > dp[v][s])continue;

		if (s + C[v] <= 2500){//銀貨を追加する理由があるとき
			ll ns = s + C[v];
			ll ntime = time + D[v];
			if (chmin(dp[v][ns],ntime))q.push(mp(ntime,mp(v,ns)));
		}
		for(auto e:G[v]){
			if (s < e.second.fs)continue;//払えないとき
			int nv = e.fs;
			ll ns = s - e.second.fs;
			ll ntime = time + e.sc.sc;
			if (chmin(dp[nv][ns],ntime))q.push(mp(ntime,mp(nv,ns)));
		}

	}
	for(int i = 1; i < n; i++) {
		ll res = LINF;
		for(int s = 0; s <= 2500; s++) {
			chmin(res,dp[i][s]);
		}
		cout << res << endl;
	}
}

int main(){
	cin>>n>>m>>S;
	G.resize(n);
	for(int i = 0; i < m; i++) {
		ll u,v,a,b;cin>>u>>v>>a>>b;
		u--;v--;
		G[u].pb(mp(v,mp(a,b)));
		G[v].pb(mp(u,mp(a,b)));
	}

	for(int i = 0; i < n; i++) {
		ll c,d;cin>>c>>d;
		C.pb(c);
		D.pb(d);
	}
	solve();
	return 0;
}
