#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
 
#define print(a) {for(auto xxxxx : (a)) cout << xxxxx << ' '; cout << '\n';}
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
 
ll next(){ll x; cin >> x; return x;}
const int maxn = 50 + 3, intf = 2e9;
const ll inf = 2e18, mod = 998244353;
const ld eps = 1e-6;
 
#define int ll

struct edge{
	int to , a , b;
};
 
int n , m;
vector <edge> g[maxn];
int c[maxn], d[maxn];
const int C = 4000;
ll dp[maxn][C];
 
int F(int x){
	return min(x , C - 1);
}
 
void solve(){
	int S;
	cin >> n >> m >> S;
 
	for (int i = 0; i < m ; i ++){
		int u , v , a , b;
		cin >> u >> v >> a >> b;
		u-- , v--;
		g[u].pb({v , a , b});
		g[v].pb({u , a , b});
	}
 
	for (int i = 0; i < n; i ++){
		cin >> c[i] >> d[i];
	}
 
	for (int i = 0; i < n; i ++){
		for (int j = 0; j < C; j ++){
			dp[i][j] = inf;
		}
	}
 
	dp[0][F(S)] = 0;
 
	for (int I = 0; I < 2*n; I ++){
 
		for (int i = 0; i < n; i ++){
			for (auto t : g[i]){
				for (int j = 0; j < C; j ++){
					if (t.a > j)
						continue;
 
					dp[t.to][j - t.a] = min(dp[t.to][j - t.a] , dp[i][j] + t.b);
				}
			}
		}
 
		for (int i = 0; i < n; i ++){
			for (int j = 0; j < C; j ++){
				if (j - c[i] < 0)
					continue;
 
				dp[i][j] = min(dp[i][j] , dp[i][j - c[i]] + d[i]);
			}
		}
 
	}
 
	for (int i = 1; i < n; i ++){
		ll ans = inf;
		for (int j = 0; j < C;  j ++){
			ans = min(ans , dp[i][j]);
		}
 
		cout << ans << '\n';
	}
}
 
 
signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cout.precision(20);
    
    for (int t = 1; t--;) {
    	solve();
    }
 
	return 0;
}
/*
 
 
*/