#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define rep(i,n) for (ll i = 0; i < (n); ++i)
#define vcout(v) rep(i,v.size()) cout << v[i] << " "; cout << endl
#define mcout(m) rep(j,m.size()){vcout(m[j]);}
const ll MOD = 1e9 + 7;

struct Info{ll v; ll c; ll t;};
struct DP{
	ll v; ll c; ll t;
	bool operator<(const DP& o) const{
		return t > o.t;
	}
};

int mainsolve(){

	ll n,m,s;
	cin >> n >> m >> s;
	vector<ll> a(m), b(m);
	vector<vector<Info>> to(n);
	rep(i,m){
		ll u,v;
		cin >> u >> v >> a[i] >> b[i];
		--u; --v;
		to[u].push_back(Info{v,a[i],b[i]});
		to[v].push_back(Info{u,a[i],b[i]});
	}
	vector<ll> c(n), d(n);
	rep(i,n) cin >> c[i] >> d[i];

	ll INF = 1e18;
	ll maxc = n*50; // 銀貨の枚数はこれだけあれば十分
	vector<vector<ll>> dp(n,vector<ll>(maxc,INF)); // dp[v][c]: 銀貨c枚持ってvにいる状態にするためにかかる時間 

	priority_queue<DP> q;
	q.push(DP{0,min(maxc-1,s),0});

	while(!q.empty()){
		DP now = q.top(); q.pop();
		if(now.c >= 0 && now.t >= 0 && now.t < dp[now.v][min(maxc-1,now.c)] ){
			dp[now.v][min(maxc-1,now.c)] = now.t;

			for(Info next : to[now.v]){
				q.push(DP{next.v,now.c - next.c, now.t + next.t}); // 移動
			}
			q.push(DP{now.v,now.c + c[now.v], now.t + d[now.v]}); // 換金
		}
	}
	
	rep(i,n){
		if(i==0) continue;
		ll res = INF;
		rep(j,maxc) res = min(res, dp[i][j]);
		cout << res << endl;
	}
	
	return 0;
}

int main(){

	return mainsolve();
}