#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <climits>
#define mk make_pair
#define pb push_back
#define scanf scanf_s
#define printf printf_s
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<ll, ll> pos;
const ll N = 60, MOD = 1000000007;

ll mn(ll a, ll b) {
	if (a == -1)return b;
	if (b == -1)return a;
	return min(a, b);
}

int bb(int v1) {
	if (v1 % 2 == 0)return v1 / 2 - 1;
	else return v1 / 2;
}

ll pw(ll a, ll b) {
	ll v = 1;
	for (; b > 0; b = (b >> 1), a = (a * a) % MOD) {
		if ((b & 1) > 0)v = (v * a) % MOD;
	}
	return v;
}
ll n, m, s;
pos cd[N];
vector<pair<int, pos> > g[N];
ll dp[N][(50 * 50 + 2)],vs[N][(50 * 50 + 2)];

int main() {
	cin >> n >> m >> s;
	while (m--) {
		int v1, v2, v3, v4; 
		cin >> v1 >> v2 >> v3 >> v4;
		g[v1].pb(mk(v2, mk(v3, v4)));
		g[v2].pb(mk(v1, mk(v3, v4)));
	}
	for (int i = 1; i <= n; i++)cin >> cd[i].first >> cd[i].second;
	for (int t = 2; t <= n; t++) {
		memset(dp, -1, sizeof(dp));
		memset(vs, false, sizeof(vs));
		priority_queue < pair<ll, pair<int, int> > > q;
		q.push(mk(0, mk(min(s, (ll)2501), 1)));
		while (!q.empty()) {
			if (q.top().second.second == t)
			{ cout << -q.top().first << endl; break; }
			ll v1 = -q.top().first;
			int v2 = q.top().second.first, v3 = q.top().second.second;
			q.pop();
			if (vs[v3][v2] )continue;
			dp[v3][v2] = v1;
			vs[v3][v2] = true;
			for (int i = 1;; i++) {
				ll v23 = min(v2 + cd[v3].first * i,(ll)2501),nv1= cd[v3].second * i + v1;
				if (dp[v3][v23] != -1&&dp[v3][v23]<=nv1)break;
				dp[v3][v23] = nv1;
				q.push(mk(-nv1, mk(v23, v3)));
				if (v2 + cd[v3].first * i >= 2501)break;
			}

			for (int i = 0; i < g[v3].size(); i++) {
				if (v2 - g[v3][i].second.first < 0)continue;
				ll ni = g[v3][i].first,nv1=v1+g[v3][i].second.second,nv2= v2 - g[v3][i].second.first;
				if (dp[ni][nv2] != -1&&dp[ni][nv2]<=nv1)continue;
				q.push(mk(-nv1, mk(nv2, ni)));
				dp[ni][nv2] = nv1;
			}
		}
	}
	return 0;
}
