// https://atcoder.jp/contests/abc164/tasks/abc164_e
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef pair<int,int> P;
#define MAX_N 55
#define MAX_M 105
#define MAX_A 55
struct EDGE{int to,cost,time;};
struct NODE{int gain,time;};
vector<EDGE> edge[MAX_N]; 
NODE node[MAX_N];
ll dp[MAX_N][MAX_N*MAX_A];
const ll INF = 1e18;
int main() {
	int n,m,s;
	cin >> n >> m >> s;
	int cmax=0;
	rep(i,m){
		int from,to,c,t;
		cin >> from >> to >> c >>t;
		from--;to--;
		edge[from].push_back((EDGE){to,c,t});
		edge[to].push_back((EDGE){from,c,t});
		if(c>cmax)cmax=c;
	}
	cmax *= n;
	rep(i,n){
		int g,t;
		cin >> g >>t;
		node[i] = (NODE){g,t};
	}
	rep(i,n)rep(j,cmax) dp[i][j] = INF;
	rep(j,cmax){
		if(j<=s)dp[0][j]=0;
		else dp[0][j] = node[0].time * ((j-s)/node[0].gain+1);
	}
	while(true){
		bool updated = false;
		for(int i=0;i<n;i++){
			rep(j,cmax){
				for(int t=1;j-t*node[i].gain>=0;t++){
					ll stay_t = dp[i][j-t*node[i].gain]+t*node[i].time;
					if(stay_t < dp[i][j]){
						dp[i][j] = stay_t;
						updated=true;
					}

				}
				rep(v,edge[i].size()){
					ll move_t = dp[edge[i][v].to][min(cmax-1,j+edge[i][v].cost)]+edge[i][v].time;
					if(move_t < dp[i][j]){
						dp[i][j] = move_t;
						updated = true;
					}
				}
			}
		}
		if(!updated) break;
	}
	for(int i=1;i<n;i++){
		ll t_min=INF;
		rep(j,cmax)t_min = min(t_min,dp[i][j]);
		cout << t_min << endl;
	}


    return 0;
}

