#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include<algorithm>
#include<string>
#include <map>
#include <queue>
#include <stack>
#include<set>
#include<math.h>

#define DIV 1000000007
using namespace std;
using ll = long long;

int main(void) {
	int N, M, S;
	cin >> N >> M >> S;

	vector < vector<pair<int, pair<ll, ll>>>> city(N + 1);
	for (int i = 0; i < M; i++) {
		int u, v;
		ll a, b;
		cin >> u >> v >> a >> b;
		city[u].push_back(make_pair(v, make_pair(-a, b)));
		city[v].push_back(make_pair(u, make_pair(-a, b)));
	}

	for (int i = 1; i <= N; i++) {
		ll c, d;
		cin >> c >> d;
		city[i].push_back(make_pair(i, make_pair(c, d)));
	}

	S = min(S, 2500);
	priority_queue<pair<ll, pair<int, int>>, vector<pair<ll, pair<int, int>>>, greater<pair<ll, pair<int, int>>>> pq;
	vector<vector<ll>> cost(N + 1, vector<ll>(2501, 1e15));
	vector<vector<bool>> visit(N + 1, vector<bool>(2501));
	pq.emplace(0, make_pair(1, S));
	cost[1][S] = 0;

	//cout << endl;
	while (!pq.empty()) {
		pair<ll, pair<int, int>> x = pq.top();
		pq.pop();
		visit[x.second.first][x.second.second] = true;

		//cout << x.second.first << " " << x.second.second << endl;
		for (auto edge : city[x.second.first]) {
			int to = edge.first, silver = min((ll)2500, x.second.second + edge.second.first);
			//cout << to << " " << silver << endl;
			if (silver < 0) continue;
			if (visit[to][silver]) continue;
			if (cost[to][silver] >cost[x.second.first][x.second.second] + edge.second.second) {
				cost[to][silver] = cost[x.second.first][x.second.second] + edge.second.second;

				pq.emplace(cost[to][silver], make_pair(to,silver));
			}

		}
	}

	for (int i = 2; i <= N; i++) {
		ll ans = 1e15;
		for (int j = 0; j <= 2500; j++) {
			ans = min(ans, cost[i][j]);
		}

		cout << ans << endl;
	}
}
