/*author : Yashvardhan
Thursday, April 30, 2020
12:12 AM
*/

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define int ll
#define pb push_back
#define vi vector<int>
#define pi pair<int,int>
#define vpi vector<pi>
#define ff first
#define ss second
#define mp make_pair
#define endl '\n'
#define all(a) a.begin(), a.end()
#define initialise(a, x) memset(a, x, sizeof(a))
#define rev(Y) reverse(all(Y))

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define _CRT_SECURE_NO_WARNINGS

#ifdef __APPLE__
#define debug(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){cerr << name << " : " << arg1 << endl;}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');
	cerr.write(names, comma - names) << " : " << arg1 << "  ";
	__f(comma + 1, args...);}
#else
#define debug(...)
#endif

template <typename T> ostream& operator << (ostream& os,const vector<T>& v){for(int i=0;i<v.size();++i) os<<v[i]<<" ";return os;} 
template <typename T> ostream& operator << (ostream& os,const set<T>& v){for(auto it:v) os<<it<<" ";return os;} 
template <typename T, typename S> ostream& operator << (ostream& os, const pair<T,S>& v) {os<<v.ff<<" "<<v.ss;return os;}

const int mod = 1e9 + 7;
const int inf = 2e18;
const int ninf = -2e18;

int takemod(int a){return ((a%mod)+mod)%mod;}

int pow(int a, int b, int m)
{
	int ans = 1;
	a %= m;
	while (b)
	{
		if (b & 1)
			ans = (ans * a) % m;
		b /= 2;
		a = (a * a) % m;
	}
	return ans;
}

int modinv(int a){return takemod( pow( takemod(a), mod-2,mod ) );}

const int N = 51;
const int M = 101;
pi arr[N];

struct edge{
	int dest, cost, time; 

	edge(int d, int c, int t){
		dest = d;
		cost = c;
		time = t;
	}
};

vector<edge> g[M];

int vis[N * 2501];
int disti[N * 2501];
map<pi,int> mapi;
map<int,pi> rmapi;
map<int,int> used;

const int MAX_REQ = 2500;

void dijkstra(pi source){
	for(int i = 0;  i < N * 2501; i++) disti[i] = inf;
	
	disti[mapi[source]] = 0;
	priority_queue<pi, vector<pi>, greater<pi>> pq;

	pq.push({0, mapi[source]});
	while(!pq.empty()){
		pi tmp = pq.top();
		pq.pop();
		int u = tmp.ss;
		int d = tmp.ff;
		if(vis[u]) continue;
		vis[u] = 1;
		
		tmp = rmapi[u];
		int curr_source = tmp.ff;
		int coins_held = tmp.ss;

		int min_purchase = arr[curr_source].ff;
		int purchase_time = arr[curr_source].ss;

		int diff = MAX_REQ - coins_held;
		int bound = diff/min_purchase;
		if(diff % min_purchase) bound++;

		
		if(!used[u]){
			for(int i = 1; i <= bound; i++){
				int new_coins_held = min(MAX_REQ, coins_held + min_purchase * i);
				int nxt_ind = mapi[{curr_source, new_coins_held}];
				if(!used[nxt_ind]){
					pq.push({d + purchase_time * i, nxt_ind});
					used[nxt_ind] = 1;
				}
			}
		}
		
		
		for(auto i : g[curr_source]){
			int nxt = i.dest;
			int cost = i.cost;
			int time = i.time;
			if(cost > coins_held) continue;
			int nxt_ind = mapi[{nxt,coins_held - cost}];
			if(disti[nxt_ind] > d + time){
				disti[nxt_ind] = d + time;
				pq.push({disti[nxt_ind], nxt_ind});
			}
		}
	}
}

signed main()
{

	ios_base::sync_with_stdio(false);
	cin.tie(0);

	#ifdef __APPLE__
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
		freopen("error.txt","w",stderr);
	#endif

	time_t t1, t2;
	t1 = clock();
	
	int n,m,s;
	cin >> n >> m >> s;

	for(int i = 1; i <= m; i++){
		int u,v,a,b;
		cin >> u >> v >> a >> b;
		g[u].pb(edge(v,a,b));
		g[v].pb(edge(u,a,b));
	}

	for(int i = 1; i <= n; i++){
		int c,d;
		cin >> c >> d;
		arr[i] = {c,d};
	}

	int ct = 1;
	for(int i = 1; i <= n; i++){
		for(int j = 0; j <= MAX_REQ; j++){
			mapi[{i,j}] = ct;
			rmapi[ct++] = {i,j};
		}
	}

	dijkstra({1,min(MAX_REQ,s)});

	for(int i = 2; i <= n; i++){
		int ans = inf;
		for(int j = 0; j <= MAX_REQ; j++){
			ans = min(ans,disti[mapi[{i,j}]]);
		}
		cout << ans << endl;
	}

	t2 = clock();
	cerr << endl << t2-t1 << endl;
	
	return 0;
}



Measured memory_bytes: 31768