#include<bits/stdc++.h>
#define fo(i,a,b) for((i)=(a);i<=(b);i++)
#define rfo(i,a,b) for((i)=(a);i>=(b);i--)
#define inrange(x,y,z) (((x)>=(y))&&((x)<=(z)))
#define ALL(vec) ((vec).begin(),(vec).end())
#define SOR(vec) sort(ALL(vec))
#define UNI(vec) (vec).erase(unique(ALL(vec)),(vec).end())
#define par pair<int,pair<int,long long> > 
#define dat pair<long long,pair<int,int> > 
using namespace std;
int n,m,s,mx,ns,a;
long long u,v,t,nt,b,c[100],d[100];
vector<par> ga[60];
long long dp[60][2510],res;
bool vis[60][2510];
priority_queue<dat,vector<dat>,greater<dat> >q; 
dat tmp;
int main(){
	#ifdef FILIN
		#ifndef DavidDesktop
			freopen(FILIN,"r",stdin);
			freopen(FILOUT,"w",stdout);
		#endif
	#endif
	ios::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>m>>s;
  	mx=(n-1)*50;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>a>>b;
		ga[u].push_back(make_pair(v,make_pair(a,b)));
		ga[v].push_back(make_pair(u,make_pair(a,b)));
	}
	for(int i=1;i<=n;i++)
		cin>>c[i]>>d[i];
	memset(dp,63,sizeof(dp));
	s=min(s,mx);
	dp[1][s]=0;
	q.push(make_pair(0,make_pair(1,s)));
	while(q.size()){
		tmp=q.top();
		q.pop();
		u=tmp.second.first;
		t=tmp.first;
		s=tmp.second.second;
		for(int i=0;i<ga[u].size();i++){
			if(s<ga[u][i].second.first) continue;
			v=ga[u][i].first;
			ns=s-ga[u][i].second.first;
			nt=ga[u][i].second.second;
			if(dp[v][ns]>dp[u][s]+nt){
				dp[v][ns]=dp[u][s]+nt;
				q.push(make_pair(dp[v][ns],make_pair(v,ns)));
			}
		}
		ns=s+c[u];
		ns=min(ns,mx);
		if(dp[u][ns]>dp[u][s]+d[u]){
			dp[u][ns]=dp[u][s]+d[u];
			q.push(make_pair(dp[u][ns],make_pair(u,ns)));
		}
	}
	for(int i=2;i<=n;i++){
		res=1e18;
		for(int j=0;j<=mx;j++){
			res=min(res,dp[i][j]);
		}
		cout<<res<<endl;
	}
	return 0;
}
