#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <functional>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <cassert>
#define InfL 1000000000
#define InfLL 1000000000000000000LL
#define nmax_def 220000
#define mod 1000000007
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<db> vd;

const int coin_max = 3000;

class Graph_class {
public:
	int N, M;
	vector<pii> edgelist;
	vl edgecost;
	vl edgetime;
	vector<vi> adjlist;
	vector<vl> adjlist_cost;
	vector<vl> adjlist_time;
	vi adjnum;

	vector<vl> time_min;

	// -------
	ll coin_ini;
	vi coin_exchange;
	vl time_exchange;
	// -------

	void read_edge();
	void adjini();
	void Dijkstra(int x);
	void solve();
};

void Graph_class::read_edge() {
	cin >> N;
	cin >> M;
	cin >> coin_ini;
	coin_ini = min(coin_ini, (ll)coin_max);
	edgelist.resize(M);
	edgecost.resize(M);
	edgetime.resize(M);
	coin_exchange.resize(N);
	time_exchange.resize(N);
	rep(i, M) {
		cin >> edgelist[i].first >> edgelist[i].second >> edgecost[i] >> edgetime[i];
		edgelist[i].first--;
		edgelist[i].second--;
	}
	rep(i, N)
		cin >> coin_exchange[i] >> time_exchange[i];
	return;
}


void Graph_class::adjini() {
	adjnum.resize(N);
	time_min.resize(N);
	adjlist.resize(N);
	adjlist_cost.resize(N);
	adjlist_time.resize(N);
	rep(i, N) {
		time_min[i].resize(coin_max + 10, InfLL);
		adjnum[i] = 0;
	}
	rep(i, M) {
		int x = edgelist[i].first;
		int y = edgelist[i].second;
		adjlist[x].push_back(y);
		adjlist[y].push_back(x);
		adjlist_cost[x].push_back(edgecost[i]);
		adjlist_cost[y].push_back(edgecost[i]);
		adjlist_time[x].push_back(edgetime[i]);
		adjlist_time[y].push_back(edgetime[i]);
		adjnum[x]++;
		adjnum[y]++;
	}
	return;
}

void Graph_class::Dijkstra(int Vini) {
	// tuple <time, V, coin>
	priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<tuple<ll, int, int>> > time_prrque;
	time_min[Vini][coin_ini] = 0;
	time_prrque.push(make_tuple(0, Vini, coin_ini));
	while (!time_prrque.empty()) {
		// 最小時間で行かれる都市と銀貨の組を決定
		tuple<ll, int, int> dist_que_tmp = time_prrque.top();
		time_prrque.pop();
		ll time_tmp = get<0>(dist_que_tmp);
		int Vtmp = get<1>(dist_que_tmp);
		int coin_tmp = get<2>(dist_que_tmp);
		if (time_min[Vtmp][coin_tmp] == time_tmp) {
			rep(i, adjnum[Vtmp] + 1) {
				ll time_new = time_tmp;
				int coin_new = coin_tmp;
				int Vnew;

				if (i == adjnum[Vtmp]) {
					// 近傍1 : 移動せず銀貨を1セット買う
					Vnew = Vtmp;
					time_new = time_tmp + time_exchange[Vtmp];
					coin_new = min(coin_tmp + coin_exchange[Vtmp], coin_max); // 過剰な銀貨は捨てる
				}

				else {
					// 近傍2 : 隣の都市に移動する
					Vnew = adjlist[Vtmp][i];
					time_new += adjlist_time[Vtmp][i];
					coin_new -= adjlist_cost[Vtmp][i];
					if (coin_new < 0)
						continue; // 銀貨の枚数が負になる経路は不可
				}
				if (time_min[Vnew][coin_new] > time_new) {
					time_min[Vnew][coin_new] = time_new;
					time_prrque.push(make_tuple(time_new, Vnew, coin_new));
				}
			}
		}
	}

	rep(i, N) {
		if (i == 0)
			continue;
		ll anstmp = InfLL;
		rep(c, coin_max + 10)
			anstmp = min(anstmp, time_min[i][c]);
		cout << anstmp << "\n";
	}

	return;
}

void Graph_class::solve() {
	Dijkstra(0);
	return;
}

int main(void) {
	Graph_class graph;
	graph.read_edge();
	graph.adjini();
	graph.solve();
	return 0;
}

Measured memory_bytes: 6568