#include<bits/stdc++.h>
using namespace std;
long long n,m,dp[53][2503],s;
vector<pair<long long,pair<long long,long long> > >v[53];
int main(){
	scanf("%lld%lld%lld",&n,&m,&s);
	s=min(s,n*50);
	while(m--){
		long long x,y,a,b;scanf("%lld%lld%lld%lld",&x,&y,&a,&b);
		v[x-1].push_back(make_pair(y-1,make_pair(-a,b)));
		v[y-1].push_back(make_pair(x-1,make_pair(-a,b)));
	}
	memset(dp,31,sizeof(dp));
	for(long long i=0;i<n;i++)
	{
		long long c,d;cin>>c>>d;
		v[i].push_back(make_pair(i,make_pair(c,d)));
	}
	priority_queue<pair<long long,pair<long long,long long> > >Q;
	Q.push(make_pair(0,make_pair(0,s)));
	dp[0][s]=0;
	while(Q.size()){
		long long tm=-Q.top().first,ct=Q.top().second.first,cn=Q.top().second.second;Q.pop();
		for(long long i=0;i<v[ct].size();i++){
			long long nct=v[ct][i].first,ntm=tm-v[ct][i].second.second,ncoi=v[ct][i].second.first+cn;
			if(ncoi<0)continue;
			if(ncoi>n*50)continue;
			if(dp[nct][ncoi]<=-ntm)continue;
			dp[nct][ncoi]=-ntm; 
			Q.push(make_pair(-ntm,make_pair(nct,ncoi)));
		}
	}
	for(long long i=1;i<n;i++){
		long long ans=LONG_LONG_MAX;
		for(long long j=0;j<=n*50;j++)ans=min(ans,dp[i][j]);
		cout<<ans<<endl;
	}
}