//#pragma GCC optimize ("O3")
//#pragma GCC target ("avx")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

constexpr int bm = 2500;
ll BIT[51][bm];
void add(int A, int gin, ll co) {
	co = 4e12 - co;
	while (gin > 0) {
		BIT[A][gin] = max(BIT[A][gin], co);
		gin -= gin & -gin;
	}
}
ll query(int A, int gin) {
	ll kotae = 0;
	while (gin < bm) {
		kotae = max(BIT[A][gin], kotae);
		gin += gin & -gin;
	}
	return 4e12 - kotae;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);


	int N, M, S;
	cin >> N >> M >> S;
	if (S >= 2460) S = 2460;

	vector<ll> E[51];
	rep(i, M) {
		int u, v, a;
		ll b;
		cin >> u >> v >> a >> b;
		b = a << 8 | b << 16;
		E[u].pb(v | b);
		E[v].pb(u | b);
	}
	int C[51], D[51];
	rep1(i, N) {
		cin >> C[i] >> D[i];
	}

	add(1, S + 1, 0);
	priority_queue<ll, vector<ll>, greater<ll> > PQ;
	PQ.push((1 << 12) + S + 1);

	while (PQ.size()) {
		auto p = PQ.top();
		PQ.pop();
		ll ti = p >> 18;
		int i = p >> 12 & 63;
		int gin = p & 4095;



		if (ti > query(i, gin)) continue;

		ll ti2 = ti + D[i];
		int gin2 = gin + C[i];
		if (gin2 > 2460) gin2 = 2460;
		if (ti2 < query(i, gin2)) {
			add(i, gin2, ti2);
			PQ.push(ti2 << 18 | i << 12 | gin2);
		}

		for (auto pp : E[i]) {
			int to = pp & 255;
			ti2 = ti + (pp >> 16);
			gin2 = gin - (pp >> 8 & 255);
			if (gin2 > 0) {
				if (ti2 < query(to, gin2)) {
					add(to, gin2, ti2);
					PQ.push(ti2 << 18 | to << 12 | gin2);
				}
			}
		}

	}

	for (int i = 2; i <= N; i++) {
		co(query(i, 1));
	}



	Would you please return 0;
}