#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<map>
#include<string.h>
#include<complex>
#include<math.h>
#include<queue>
#include <functional>
#include<time.h>
#include <stack>
#include<iomanip>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define ll long long
#define llint long long int
#define reverse(v)  reverse(v.begin(), v.end());
#define Yes(ans) if(ans)cout<<"Yes"<<endl; else cout<<"No"<<endl;
#define YES(ans) if(ans)cout<<"YES"<<endl; else cout<<"NO"<<endl;
#define hei(a) vector<a>
#define whei(a) vector<vector<a>>
#define UF  UnionFind 
#define Pint pair<int,int>
#define Pll pair<llint,llint>
#define keta(a)  fixed << setprecision(a)
constexpr auto INF = 1000000000000000000;
constexpr auto mod = 1000000007;
//辞書順はnext_permutation( begin( v ), end( v ) );やで！

struct edge { int to;llint kane, cost; };
struct usi { llint v, c; llint t; };
whei(edge) G;
hei(llint) C, D;
llint sum;
void dijkdtra(vector<vector<llint>>& d, llint s) {
	priority_queue<usi, vector<usi>, greater<usi>> que;
	d[0][s] = 0;//スタートの距離はもちろんzero
	que.push(usi{0, (int)s, 0});
	auto push = [&](int v, int c, int t) {
		if (c < 0)return;
		if (d[v][c] <= t)return;
		d[v][c] = t;
		que.push(usi{ v,c,t });
	};
	while (!que.empty()) {
		usi p = que.top();
		que.pop();
		int V = p.v;
		llint a = min(C[V] + p.c, sum);
		push(p.v, a, p.t+ D[V]);
		for (edge x : G[V])push(x.to, p.c - x.kane, p.t + x.cost);
	}
}

signed  main() {
	int n, m;
	cin >> n >> m;
	llint s;
	cin >> s;
	G.resize(n);
	rep(i, 0, m) {
		int v, u;
		llint a, b;
		cin >> u >> v >> a >> b;
		u--; v--;
		G[u].push_back(edge{ v,a,b });
		G[v].push_back(edge{ u,a,b });
	}
	sum = (n - 1) * 50;
	rep(i, 0, n)cin >> C[i] >> D[i];
	whei(llint) d(n, hei(llint)(sum + 1, INF));

	s = min(s,sum);
	dijkdtra(d, s);
	rep(i, 1, n) {
		llint ans = INF;
		rep(j, 0, sum + 1)ans = min(ans, d[i][j]);
		cout << ans << endl;
	}
	return 0;
}