#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;

int coin_max = 3000;

class Graph_class {
public:
	bool graph_from1 = true;
	bool graph_tree = false;
	bool graph_weight = true;
	bool graph_digraph = false;
	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> xdist;

	// -------
	ll S;
	vl A, B, D;
	vi C;
	// -------

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

void Graph_class::read_edge() {
	cin >> N;
	cin >> M;
	cin >> S;
	S = min(S, (ll)coin_max);
	edgelist.resize(M);
	edgecost.resize(M);
	edgetime.resize(M);
	C.resize(N);
	D.resize(N);
	rep(i, M) {
		cin >> edgelist[i].first >> edgelist[i].second >> edgecost[i] >> edgetime[i];
		if (graph_from1) {
			edgelist[i].first--;
			edgelist[i].second--;
		}
	}
	rep(i, N)
		cin >> C[i] >> D[i];
	return;
}


void Graph_class::adjini() {
	adjnum.resize(N);
	xdist.resize(N);
	rep(i, N)
		xdist[i].resize(coin_max + 10, InfLL);
	adjlist.resize(N);
	adjlist_cost.resize(N);
	adjlist_time.resize(N);
	rep(i, N)
		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;
}

typedef struct {
	int V;
	int coin;
}Graph_nei;

Graph_nei P_to_Q(ll P) {
	Graph_nei Q;
	Q.coin = P % InfL;
	Q.V = P / InfL;
	return Q;
}

ll Q_to_P(Graph_nei Q) {
	ll P;
	P = (ll)Q.coin + (ll)Q.V * InfL;
	return P;
}

void Graph_class::Dijkstra(int x) {
	priority_queue<pll, vector<pll>, greater<pll> > dist_que;
	xdist[x][S] = 0;
	pair<ll, Graph_nei> dist_que_tmp;
	dist_que_tmp.first = 0;
	dist_que_tmp.second.V = x;
	dist_que_tmp.second.coin = S;
	pll dist_que_P = make_pair(dist_que_tmp.first, Q_to_P(dist_que_tmp.second));
	dist_que.push(dist_que_P);
	while (!dist_que.empty()) {
		// 最小時間で行かれる都市と銀貨の組を決定
		dist_que_P = dist_que.top();
		dist_que.pop();
		ll dist_tmp = dist_que_P.first;
		int Vtmp = P_to_Q(dist_que_P.second).V;
		int coin_tmp = P_to_Q(dist_que_P.second).coin;
		if (xdist[Vtmp][coin_tmp] == dist_tmp) {
			rep(i, adjnum[Vtmp] + 1) {
				ll dist_new = dist_tmp;
				int coin_new = coin_tmp;
				int Vnew;

				if (i == adjnum[Vtmp]) {
					// 近傍1 : 移動せず銀貨を1セット買う
					Vnew = Vtmp;
					dist_new = dist_tmp + D[Vtmp];
					coin_new = min(coin_tmp + C[Vtmp], coin_max);
				}

				else {
					// 近傍2 : 隣の都市に移動する
					Vnew = adjlist[Vtmp][i];
					dist_new += adjlist_time[Vtmp][i];
					coin_new -= adjlist_cost[Vtmp][i];
					if (coin_new < 0)
						continue; // 銀貨の枚数が負になる経路は不可
				}
				if (xdist[Vnew][coin_new] > dist_new) {
					xdist[Vnew][coin_new] = dist_new;
					dist_que_tmp.first = dist_new;
					dist_que_tmp.second.V = Vnew;
					dist_que_tmp.second.coin = coin_new;
					dist_que_P = make_pair(dist_que_tmp.first, Q_to_P(dist_que_tmp.second));
					dist_que.push(dist_que_P);
				}
			}

		}
	}

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

	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: 6572