#include <bits/stdc++.h>
using namespace std;
using lint = long long;
lint N, M, S;
typedef pair<lint, lint> P;
using edge = pair<lint, P>;
vector<vector<edge> > G;
vector<lint> c, d;
const lint MAX_MONEY = 2500, INF = 1e18;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

void solve(){
	if(S >= MAX_MONEY) S = MAX_MONEY;
	vector<vector<lint> > dp(N, vector<lint> (MAX_MONEY + 10, INF));
	priority_queue<pair<lint, P>, vector<pair<lint, P> >, greater<pair<lint, P> > > que;
	dp[0][S] = 0;
	que.push(make_pair(0, P(0 ,S)));
	while(que.size()){
		auto p = que.top(); que.pop();
		lint time = p.first, now = p.second.first, money = p.second.second;
		if(time > dp[now][money]) continue;

		if(money + c[now] <= MAX_MONEY){
			lint ns = money + c[now];
			lint ntime = time + d[now];
			if(chmin(dp[now][ns], ntime)) que.push(make_pair(ntime, P(now, ns)));
		}

		for(auto e : G[now]){
			if(money < e.second.first) continue;
			lint nv = e.first;
			lint ns = money - e.second.first;
			lint ntime = time + e.second.second;
			if(chmin(dp[nv][ns], ntime)) que.push(make_pair(ntime, P(nv, ns)));
		}
	}

	for(lint v = 1; v < N; v++){
		lint ans = INF;
		for(lint s = 0; s <= MAX_MONEY; s++) ans = min(ans, dp[v][s]);
		cout << ans << endl;
	}
}

signed main(){
	cin >> N >> M >> S;
	c.resize(N); d.resize(N); G.resize(N);
	for(lint i = 0; i < M; i++){
		lint u, v, a, b; cin >> u >> v >> a >> b; --u; --v;
		G[u].push_back(edge(v, P(a, b)));
		G[v].push_back(edge(u, P(a, b)));
	}
	for(lint i = 0; i < N; i++) cin >> c[i] >> d[i];
	solve();
}