#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>
#include<utility>
#include<queue>

using namespace std;

#define int long long
#define endl "\n"

constexpr long long INF = (long long)1e18;
constexpr long long MOD = 1'000'000'007; 

struct fast_io {
	fast_io(){
		std::cin.tie(nullptr);
		std::ios::sync_with_stdio(false);
	};
// } ;
} fio;

void dijkstra(int s, vector<int> &d, vector<vector<pair<int,int>>> &G){
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
	
	d.clear();
	d.resize(G.size(),INF);
	d[s] = 0;
	q.push(make_pair(0,s));
	
	while(!q.empty()){
		pair<int,int> p = q.top();q.pop();
		int v = p.second;
		
		if(d[v] < p.first) continue;
		
		for(pair<int,int> e : G[v]){
			if(d[e.first] > d[v] + e.second){
				d[e.first] = d[v] + e.second;
				q.push(make_pair(d[e.first],e.first));
			}
		}
	}	
}

signed main(){
	cout<<fixed<<setprecision(10);
	
	const int maxA = 52;
	int N, M, S;
	int Z;
	vector<int> d;
	vector<vector<pair<int,int>>> G;
	vector<vector<pair<int,pair<int,int>>>> g;
	
	cin>>N>>M>>S;
	
	Z = M * maxA;
	
	G.resize(N * Z);
	g.resize(N);
	
	
	for(int i = 0; i < M; i++){// cout<<i<<endl;
		int U, V, A, B;
		
		cin>>U>>V>>A>>B;
		
		U--, V--;
		
		g[U].push_back({V,{A,B}});
		g[V].push_back({U,{A,B}});
	}
	
	for(int i = 0; i < N; i++){
		int C, D;
		
		cin>>C>>D;
		
		for(int j = 0; j < Z; j++){
			for(int k = 0; k < g[i].size(); k++){
				int A = g[i][k].second.first;
				int B = g[i][k].second.second;
				if(j - A < 0) continue;
				G[i * Z + j].push_back({g[i][k].first * Z + j - A, B});
				// G[g[i][k].first * Z + j - g[i][k].second.first ].push_back({i * Z + j,g[i][k].second.second});
			}
		}
		
		for(int j = 0; j < Z; j++){
			G[i * Z + j].push_back({i * Z + min(Z-1, j + C),D});
		}
	}
	
	S = min(S, Z-1);
	
	dijkstra(Z * 0 + S, d, G);
	
	
	for(int i = 1; i < N; i++){
		int ans = INF;
		for(int j = 0; j < Z; j++){
			ans = min(ans, d[i * Z + j]);
		}
		
		cout<<ans<<endl;
	}
	
	return 0;
}