#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<bitset>
#include<time.h>
#include<string>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#define ui unsigned int
//ios::sync_with_stdio(false);
#define ull unsigned long long
#define endl "\n"
#define int long long
#define double long double
#define jn jnn
using namespace std;
#define PI  3.1415926535898
const double eqs = 1e-6;
const long long max_ = 60 + 7;
const int mod = 1e9 + 7;
const int inf = 1e9 + 7;
const long long INF = 1e18;
inline int read() {
	int s = 0, f = 1;
	char ch = getchar();
	while (ch<'0' || ch>'9') {
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (ch >= '0'&&ch <= '9') {
		s = s * 10 + ch - '0';
		ch = getchar();
	}
	return s * f;
}
inline void write(int x) {
	if (x < 0) {
		putchar('-');
		x = -x;
	}
	if (x > 9)
		write(x / 10);
	putchar(x % 10 + '0');
}
inline int min(int a, int b) {
	return a < b ? a : b;
}
inline int max(int a, int b) {
	return a > b ? a : b;
}
int n, m, s;
int f[60][140000];
struct node_ {
	int now, now_coin;
	int spend_time;
	node_() {}
	node_(int a, int b, int c) {
		now = a, now_coin = b, spend_time = c;
	}
	bool operator < (const  node_& a)const {
		return spend_time > a.spend_time;
	}
};
priority_queue<node_>que;
vector<pair<int, pair<int, int> > >xian[max_];
int ans[max_], C[max_], D[max_];
int floy[max_][max_];
signed main() {
	n = read(), m = read(), s = read();
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			floy[i][j] = inf;
		}
	}
	for (int i = 1; i <= n; i++)floy[i][i] = 0;
	for (int i = 1; i <= m; i++) {
		int a = read(), b = read(), cost_ = read(), time_ = read();
		floy[a][b] = min(floy[a][b], cost_); floy[b][a] = min(floy[b][a], cost_);
		xian[a].push_back(make_pair(b, make_pair(cost_, time_)));
		xian[b].push_back(make_pair(a, make_pair(cost_, time_)));
	}
	int limit = -inf;
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				floy[i][j] = min(floy[i][j], floy[i][k] + floy[k][j]);
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			limit = max(floy[i][j], limit);
		}
	}limit += 200;

	s = min(s, limit);
	for (int i = 1; i <= n; i++) {
		C[i] = read();
		D[i] = read();
	}
	que.push(node_(1, s, 0));
	memset(f, 127, sizeof(f)); memset(ans, 127, sizeof(ans));
	f[1][s] = 0;
	while (!que.empty()) {
		node_ tou = que.top(); que.pop();
		if (f[tou.now][tou.now_coin] != tou.spend_time)continue;
		ans[tou.now] = min(ans[tou.now], tou.spend_time);
		int v = min(limit, C[tou.now]),nowmin = f[tou.now][0];
		for (int i = 1; i <= limit; i++) {
			if (i - v >= 0) {
				f[tou.now][i] = min(f[tou.now][i - v] + D[tou.now], f[tou.now][i]);
			}
			else {
				f[tou.now][i] = min(f[tou.now][i], nowmin + D[tou.now]);
			}
			nowmin = f[tou.now][i];
			for (auto pa : xian[tou.now]) {
				int to = pa.first;  auto p = pa.second;
				int cost_ = p.first, time_ = p.second;
				if (cost_ <= i) {
					if (f[to][i - cost_] > f[tou.now][i] + time_) {
						f[to][i - cost_] = f[tou.now][i] + time_;
						que.push(node_(to, i - cost_, f[tou.now][i] + time_));
					}
				}
			}
		}
	}
	for (int i = 2; i <= n; i++) {
		printf("%lld\n", ans[i]);
		//cout << ans[i] << endl;
	}
	return 0;
}


Measured memory_bytes: 71988