#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <numeric>
#include <list>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <tuple>

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i <= (n); i++)
#define show(a, n) rep(i,n) {cout<<a[i]<<' ';} cout<<endl
#define show2(a, n, m) rep(i, n) { rep(j, m) {cout << a[i][j] << ' ';} cout << endl;} 
#define chmin(a, b) a = min(a, b)
#define chmax(a, b) a = max(a, b)

using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<long long, long long> pll;
typedef long double ld;

const int INF = 1 << 30;
const long long INFL = 1LL << 60;
const int MOD = 1000000007;
const int MAX = 100000;
const int N = 100010;

typedef tuple<ll, ll, ll> tup3;
vector<vector<tup3>> g;	// node, cost, time
vector<vll> d;	// time, coin
ll cmax;

void dijkstra(ll s) {
	priority_queue<tup3, vector<tup3>, greater<tup3>> q;	// time, node, coin
	q.push(make_tuple(0, 0, min(s, cmax)));
	d[0][min(s, cmax)] = 0;
	while(!q.empty()) {
		ll cur_time, cur_node, coin;
		tie(cur_time, cur_node, coin) = q.top();
		q.pop();
		for(auto i: g[cur_node]) {
			ll nxt_node, cost, taken_time;
			tie(nxt_node, cost, taken_time) = i;
			if(coin < cost) continue;
			ll nxt_coin = min(coin - cost, cmax);
			if(d[nxt_node][nxt_coin] <= cur_time + taken_time) continue;
			q.push(make_tuple(cur_time + taken_time, nxt_node, nxt_coin));
			d[nxt_node][nxt_coin] = cur_time + taken_time;
		}
	}
}

int main() {
//	cout << fixed << setprecision(15);
	ll n, m, s;
	cin >> n >> m >> s;

	g = vector<vector<tup3>>(n);
	ll amax = 0;
	rep(i, m) {
		ll u, v, a, b;
		cin >> u >> v >> a >> b;
		u--, v--;
		g[u].push_back(make_tuple(v, a, b));
		g[v].push_back(make_tuple(u, a, b));
		chmax(amax, a);
	}
	rep(i, n) {
		ll c, d;
		cin >> c >> d;
		g[i].push_back(make_tuple(i, -c, d));
	}

	cmax = amax * n + 1;
	d = vector<vll>(n, vll(cmax, INFL));
	dijkstra(s);
	rep1(i, n - 1) {
		ll ans = INFL;
		rep(j, cmax) chmin(ans, d[i][j]);
		cout << ans << endl;
	}
}
