#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
#define all(x) (x).begin(), (x).end()
#define fsp(x) fixed << setprecision(x)
//const ll p = 1e9 + 7;
//const ll p = 998244353;
const ll inf = LLONG_MAX;
const long double pi = acos(-1);
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}

vll dijkstra(ll n, vector<vector<vll>> &nx, ll start) {
	vll ret(n * 2501, inf);
	ret[start] = 0;
	queue<ll> task;
	task.push(start);
	priority_queue<vll, vector<vll>, greater<vll>> pq;
	while (task.size()) {
		while (task.size()) {
			ll x = task.front();
			task.pop();
			for (ll i = 0; i < nx[x].size(); i++) {
				vll v = nx[x][i];
				if (ret[v[1]] < inf) continue;
				pq.push({ret[x] + v[0], v[1]});
			}
		}
		while (pq.size() && ret[pq.top()[1]] < inf) pq.pop();
		if (pq.size()) {
			vll v = pq.top();
			pq.pop();
			ret[v[1]] = v[0];
			task.push(v[1]);
		}
	}
	return ret;
}

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

	ll n, m, s;
	cin >> n >> m >> s;
	s = min(s, 2500ll);

	//頂点aで銀貨b枚所持
	auto index = [&] (ll a, ll b) {return a + b * n;};

	vector<vector<vll>> nx(n * 2501, vector<vll>(0));
	for (ll i = 0; i < m; i++) {
		ll u, v, a, b;
		cin >> u >> v >> a >> b;
		u--;
		v--;
		for (ll j = a; j <= 2500; j++) {
			nx[index(u, j)].push_back({b, index(v, j - a)});
			nx[index(v, j)].push_back({b, index(u, j - a)});
		}
	}

	for (ll i = 0; i < n; i++) {
		ll c, d;
		cin >> c >> d;
		for (ll j = 0; j <= 2500 - c; j++) {
			nx[index(i, j)].push_back({d, index(i, j + c)});
		}
	}

	vll ans = dijkstra(n, nx, index(0, s));
	for (ll i = 1; i < n; i++) {
		ll x = inf;
		for (ll j = 0; j <= 2500; j++) {
			x = min(x, ans[index(i, j)]);
		}
		cout << x << endl;
	}
}
