已经调了好久了，连对拍都试过了就是不知道哪里错了。。。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#include<cmath>
#include<set>
#include<cstdlib>
#include<cctype>
#include<ctime>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll maxn = 2e3 + 5e2 + 5;
const ll maxm = 5e1 + 5;
template<class T>
inline T qread(T &IEE){
	register T x = 0, f = 1;
	register char ch = getchar();
	while(!isdigit(ch)){
		if(ch == '-'){
			f = -f;
		}
		ch = getchar();
	}
	while(isdigit(ch)){
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return IEE = x * f;
}
template<class T>
inline void qwrite(T a){
	if(!a){
		putchar('0');
		return ;
	}
 	if(a < 0){
		putchar('-');
		a = -a;
	}
	if(a > 9) qwrite(a / 10);
	putchar(a % 10 + 48);
	return ;
}
template<class T>
inline T ab(T a){
	return (a > 0) ? a : -a;
}
template<class T>
inline void swa(T &a, T &b){
	a ^= b ^= a ^= b;
	return ;
}
ll ma, y, x, s, m, n;
ll a[maxm][maxm], b[maxm][maxm], c[maxm], d[maxm];
ll dis[maxm][maxn];
bool al[maxm][maxn];
queue<pair<ll, ll> > q;
void spfa(){
	memset(dis, 0x3f, sizeof(dis));
	dis[1][s] = 0;
	q.push(make_pair(1, s));
	al[1][s] = 1;
	while(!q.empty()){
		ll fir = q.front().first, sec = q.front().second;
//		cout << fir << " " << sec << endl;
		q.pop();
		al[fir][sec] = 0;
		for(int i = 1;i <= n;i++){
			if(!a[fir][i]){
				continue;
			}
			if(sec >= a[fir][i] && dis[i][sec - a[fir][i]] > dis[fir][sec] + b[fir][i]){
				dis[i][sec - a[fir][i]] = dis[fir][sec] + b[fir][i];
				if(al[i][sec - a[fir][i]]){
					continue;
				}
				q.push(make_pair(i, sec - a[fir][i])); 
			}
		}
		if(dis[fir][min(sec + c[fir], 2500ll)] > dis[fir][sec] + d[fir]){
			dis[fir][min(sec + c[fir], 2500ll)] = dis[fir][sec] + d[fir];
			if(al[fir][min(sec + c[fir], 2500ll)]){
				continue;
			}
			q.push(make_pair(fir, min(sec + c[fir], 2500ll))); 
		}
	} 
	return ;
}
int main(){
//	freopen("1.in", "r", stdin);
//	freopen("1.out", "w", stdout);
	qread(n);
	qread(m);
	qread(s);
	if(s > 2500){
		s = 2500;
	}
	for(int i = 1;i <= m;i++){
		qread(x);
		qread(y);
		qread(a[x][y]);
		qread(b[x][y]);
		a[y][x] = a[x][y];
		b[y][x] = b[x][y];
	}
	for(int i = 1;i <= n;i++){
		qread(c[i]);
		qread(d[i]);
	}
	spfa();
	for(int i = 2;i <= n;i++){
		ma = 0x3f3f3f3f;
		for(int j = 0;j <= 2500;j++){
			ma = min(ma, dis[i][j]);
		}
		cout << ma << endl;
	}
	return 0;
}