#include <bits/stdc++.h>

using namespace std;

#define LL long long
#define ULL unsigned LL
#define LD long double
#define debug(x) cerr << #x << " " << x << endl;

const LL INF = 1e18 + 2137;
const int N = 51 * 5002 + 2137;
vector<pair<int, LL>> V[N];
LL odl[N];

void djikstra(int src) {
	odl[src] = 0;
	set<pair<LL, int>> S;
	S.insert(make_pair((LL) 0, src));
	while(!S.empty()) {
		pair<LL, int> tmp = *(S.begin());
		S.erase(S.begin());
		int v = tmp.second;
		for(int i=0; i<V[v].size(); i++) {
			int u = V[v][i].first;
			LL waga = V[v][i].second;
			if(odl[u] > odl[v] + waga) {
				if(odl[u] != INF)
					S.erase(S.find(make_pair(odl[u], u)));
				odl[u] = odl[v] + waga;
				S.insert(make_pair(odl[u], u));
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, m, s;
	cin>>n>>m>>s;
	s = min(s, 5000);
	int u, v, a, b;
	for(int i=0; i<m; i++) {
		cin>>u>>v>>a>>b;
		for(int j=a; j<=5000; j++) {
			V[j*n+u].push_back({(j-a)*n+v, b});
			V[j*n+v].push_back({(j-a)*n+u, b});
		}
	}
	int c, d;
	for(int i=1; i<=n; i++) {
		cin>>c>>d;
		for(int j=0; (j+c) <= 5000; j++) {
			V[j*n+i].push_back({(j+c)*n+i, d});
		}
	}
	for(int i=1; i<=n; i++) {
		for(int j=0; j<=5000; j++)
			odl[j*n+i] = INF;
	}
	int nrstartowy = s*n + 1;
	djikstra(nrstartowy);
	for(int i=2; i<=n; i++) {
		LL odlx = INF;
		for(int j=0; j<=5000; j++) {
			odlx = min(odlx, odl[j*n+i]);
		}
		cout<<odlx<<"\n";
	}
}
