#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <math.h>
#include <cmath>
#include <ctime>
#include <stdlib.h>


using namespace std;

/*
#pragma GCC target("avx2") //AtCoderでは "avx" にする
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
*/

#define int long long
#define endl "\n"
#define all(v)  v.begin(),v.end()
#define fir first
#define sec second
#define m_p make_pair
#define m_t make_tuple
#define rep(i,n)  for(int i=0; i<(int) (n); i++)
typedef pair<int, int> PP;
typedef long double ld;
typedef long long ll;

const double pai = 3.1415926535897;
const ll mod = 1000000007;
const int INF = 1000000021;
const ll LINF = 2000000000000000000;
const int MAX = 510000;
const ll MOD = 1000000007;
long long fac[MAX], finv[MAX], inv[MAX];


// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}
//n個を1個以上のx組のグループに分ける重複組み合わせはcom(n-1,x-1)
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
ll PER(int n, int k) {
	if (n < 0 || k < 0) return 0;
	if (n < k) return fac[n];
	return fac[n] * finv[n - k] % mod;
}

long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
long long modpow(int a, int n) {
	int res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}


struct edge {
	int to, cost,time;
};
edge m_e(int xx, int yy,int zz) {
	edge ed;
	ed.to = xx;
	ed.cost = yy;
	ed.time = zz;
	return ed;
}
//x未満の要素数を返す二分探索関数
int b_s(vector<int>& vec, int xx) {
	return lower_bound(all(vec), xx) - vec.begin();
}
template<typename T>void vecout(vector<T>& vec) { for (T t : vec) cout << t << " "; cout << endl; }
template<typename TT>void vecin(vector<TT>& vec) {
	for (int i = 0; i < vec.size(); i++) {
		cin >> vec[i];
	}
}
bool chmax(int& xx, int yy) {
	if (xx < yy) {
		xx = yy;
		return true;
	}
	return false;
}
bool chmin(int& xx, int yy) {
	if (xx > yy) {
		xx = yy;
		return true;
	}
	return false;
}
double dist(int x, int y) {
	return sqrt(x * x + y * y);
}
double dist(int xx1, int xx2, int yy1, int yy2) {
	return sqrt(abs(xx1 - xx2) * abs(xx1 - xx2) + abs(yy1 - yy2) * abs(yy1 - yy2));
}
ll mypow(int nn, int kk) {
	ll xx = 1;
	rep(i, kk) {
		xx *= nn;
	}
	return xx;
}
int gcd(int xx, int yy) {
	int p = xx;
	int q = yy;
	if (q > p)swap(p, q);
	while (p % q != 0) {
		p %= q;
		swap(p, q);
	}
	return q;
}
int lcm(int xx, int yy) {
	return xx * yy / gcd(xx, yy);
}
bool prime(int xx) {
	if (xx <= 1) {
		return 0;
	}
	for (int i = 2; i * i <= xx; i++) {
		if (xx % i == 0) {
			return 0;
		}
	}
	return 1;
}



signed main() {
	int N, M, S,u,v,a,b,t = 0,total=0,ans=LINF;
	cin >> N >> M >> S;
	vector<vector<edge>>route(N);
	vector<PP>rate(N);//銀貨の枚数, 交換時間
	rep(i, M) {
		cin >> u >> v >> a >> b;
		total += a;
		u--;
		v--;
		route[u].push_back(m_e(v, a, b));
		route[v].push_back(m_e(u, a, b));
	}
	vector<vector<int>>minutes(N,vector<int>(total+1,LINF));//町、金貨
	rep(i, N) {
		cin >> rate[i].first >> rate[i].second;
	}
	priority_queue<pair<int, PP>,vector<pair<int,PP>>,greater<pair<int,PP>>>pque;//時間、町、金額
	pque.push(m_p(0, m_p(0, min(S,total))));
	while (!pque.empty()) {
		t = pque.top().first;
		int fi = pque.top().second.first,se=pque.top().second.second;
		pque.pop();
		if (minutes[fi][se] < t)continue;
		if (se < total) {
			if (chmin(minutes[fi][min(se + rate[fi].first, total)], t + rate[fi].second)) {
				pque.push(m_p(t + rate[fi].second, m_p(fi, min(se + rate[fi].first, total))));
			}
		}
		rep(i, route[fi].size()) {
			if (se - route[fi][i].cost < 0)continue;
			if (chmin(minutes[route[fi][i].to][se - route[fi][i].cost], t + route[fi][i].time)) {
				pque.push(m_p(t + route[fi][i].time, m_p(route[fi][i].to, se - route[fi][i].cost)));
			}
		}
	}
	for(int i=1; i<N; i++) {
		ans = LINF;
		rep(j, total + 1) {
			chmin(ans, minutes[i][j]);
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 7240