#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m, s;
typedef pair<ll, ll> P;
using edge = pair<ll, P>;
const ll INF = 1e18, MAX_COST = 2500;

signed main(){
	ll n, m, s; cin >> n >> m >> s;
	s = min(s, MAX_COST);
	vector<vector<edge> > G(n);
	for(int i = 0; i < m; i++){
		ll u, v, a, b; scanf("%lld%lld%lld%lld", &u, &v, &a, &b); --u; --v;
		G[u].push_back(edge(v, P(a, b))); G[v].push_back(edge(u, P(a, b)));
	}
	vector<ll> c(n), d(n);
	for(int i = 0; i < n; i++) scanf("%lld%lld", &c[i], &d[i]);
	vector<vector<ll> > dist(n, vector<ll> (MAX_COST + 1, INF));
	priority_queue<edge, vector<edge>, greater<edge> >  que;
	dist[0][s] = 0;
	que.push(edge(0, P(0, s)));

	while(!que.empty()){
		edge e = que.top(); que.pop();
		ll time = e.first, now = e.second.first, money = e.second.second;
		if(dist[now][money] < time) continue;

		if(money + c[now] <= MAX_COST) {
			ll ntime = time + d[now], nmoney = money + c[now];
			if(dist[now][nmoney] > ntime){
				dist[now][nmoney] = ntime;
			  que.push(edge(ntime, P(now, nmoney)));
			}
		}

		for(auto e : G[now]){
			if(money < e.second.first) continue;
			ll next = e.first, ntime = time + e.second.second, nmoney = money - e.second.first;
			if(dist[next][nmoney] > ntime){
				dist[next][nmoney] = ntime;
				que.push(edge(ntime, P(next, nmoney)));
			}
		}
	}

	for(int i = 1; i < n; i++){
		ll ans = INF;
		for(int j = 0; j <= MAX_COST; j++) ans = min(ans, dist[i][j]);
		cout << ans << endl;
	}
}
