/*
 author : Anubhav Dinesh Patel
 date : 31.05.2020 15:38:05 IST 
*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long int
#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL)
#define endl '\n'
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end() 
#define max_pqueue priority_queue< long long >
#define min_pqueue priority_queue< long long , vector<long long> , greater< long long >>
#define vi vector<int>
#define vii vector<pair<int, int>>
#define vl vector<long long>
#define vll vector<pair<long long, long long>>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define FF first
#define SS second
#define sz(x) (int)x.size()
#define gcase "Case #"<<tcase<<": "
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<int, int, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_map;

//~ setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//~ setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//~ setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//~ cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val

#ifndef LOCAL_MACHINE
#define cerr if (false) cerr
#endif

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
template<typename T>
void _printA(T *t, long long sz) { cout<<" { "; for (long long i=0; i<sz; i++) cout<<"["<<i<<"] = "<< t[i]<<endl; cout<<" } \n";}
#ifdef LOCAL_MACHINE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#define debugA(x, y) cerr << "[" << #x << "] = "; _printA(x, y)
#else
#define debug(x...)
#define debugA(x, y)
#endif

const ll _MOD = 998244353LL;

ll mod(ll a, ll m=_MOD) {
	return (a + m) % m;
}

ll gcd(ll a, ll b) { return __gcd(a, b); }

ll gcd(ll a, ll b, ll & x, ll & y) {
    if (a == 0) {
        x = 0;
        y = 1;
        return b;
    }
    ll x1, y1;
    ll d = gcd(b % a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return d;
}

ll modinv(ll a, ll m=_MOD) {
	ll x, y;
	gcd(a, m, x, y);
	x = (x % m + m) % m;
    return x;
}

ll powm(ll a, ll b, ll m=_MOD) {
	if (b == 0) return 1;
	ll ans = powm(a, b/2, m);
	ans = (ans * ans) % m;
	return (b & 1) ? (ans * (a%m)) % m : ans;
}

/* 1. If you can't keep solution in mind, then visualize it on a paper.
 * 2. Try to identify the type of problem - DP, Greedy, Graph, Constructive, 
 * 	  Prefix/Suffix, Difference Array, BIT/Segment Tree, etc.
 * 3. Divide difficult solutions into cases and/or sequences.
 * 4. Use math rules to solve Nested Summation.
 * ------------------------------------------------------------------ 
 */

struct edge {
	int dest;
	ll si, ct;
	edge(int dest, ll si, ll ct) : dest(dest), si(si), ct(ct) {}
};

vector<edge> adj[55];
vector<ll> C(55), D(55); // silver coin for 1 gold, time for 1 gold 
int N, M;
ll S;
void solve(/* int tcase */) {
	cin>>N>>M>>S;
	ll amax = -1;
	for (int i=0; i<M; i++) {
		int u, v;
		ll A, B;
		cin>>u>>v>>A>>B, u--, v--;
		amax = max(amax, A);
		adj[u].pb({v,A,B});
		adj[v].pb({u,A,B});
	}
	
	for (int i=0; i<N; i++) {
		cin>>C[i]>>D[i];
	}
	
	if (S > (N-1)*amax)
		S = (N-1)*amax;
		
	map<pll, ll> dist;
	dist[{0, S}] = 0;
	
	set<pair<ll, pll>> Q;
	Q.insert({0, {0, S}});
	while (!Q.empty()) {
		auto pp = *Q.begin();
		Q.erase(Q.begin());
		int u = pp.SS.FF;
		ll coins = pp.SS.SS;
		ll d = pp.FF;
		
		// debug(u, coins, d);
		for (auto e : adj[u]) {
			if (e.si <= coins) {
				if (dist.find({e.dest, coins - e.si}) == dist.end())
					dist[{e.dest, coins - e.si}] = LLONG_MAX;
					
				if (dist[{e.dest, coins - e.si}] > d + e.ct) {
					auto it = Q.find({dist[{e.dest, coins - e.si}], {e.dest, coins - e.si}});
					if (it != Q.end())
						Q.erase(it);
					dist[{e.dest, coins - e.si}] = d + e.ct;
					Q.insert({dist[{e.dest, coins - e.si}], {e.dest, coins - e.si}});
				}
			}
		}
		
		// ll nxt_c = coins;
		if (coins + C[u] <= (N-1)*amax) {
			if (dist.find({u, coins + C[u]}) == dist.end())
					dist[{u, coins + C[u]}] = LLONG_MAX;
				
			if (dist[{u, coins + C[u]}] > d + D[u]) {
				auto it = Q.find({dist[{u, coins + C[u]}], {u, coins + C[u]}});
				if (it != Q.end())
					Q.erase(it);
				dist[{u, coins + C[u]}] = d + D[u];
				Q.insert({dist[{u, coins + C[u]}], {u, coins + C[u]}});
			}
			
			// coins += C[u];
			// d += D[u];
		}
	}
	
	ll ans[55];
	for (int i=0; i<N; i++)
		ans[i] = LLONG_MAX;
		
	// debug(dist);
	for (auto pp : dist) {
		ans[pp.FF.FF] = min(ans[pp.FF.FF], pp.SS);  
	}
	
	for (int i=1; i<N; i++)
		cout<<ans[i]<<"\n";
	// cout<<endl;
}

void preprocess() {
	
}

int main() {
#ifdef LOCAL_MACHINE
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wunused-result"
freopen("in", "r", stdin);
#pragma GCC diagnostic pop
#endif

	fast_io;
	preprocess();
	ll T;
	T = 1;
	// cin>>T;
	for (ll t=0; t<T; t++) {
		solve(/* t */);
	}
}	


Measured memory_bytes: 13248