#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimization ("Ofast")
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define all(v) v.begin(),v.end()
#define P pair<int,int>
#define siz(s) (int)s.size()

template<class T> inline bool chmin(T &a, T b) {
	if(a>b){a=b;return true;}
	return false;
}
template<class T> inline bool chmax(T &a, T b) {
	if(a<b){a=b;return true;}
	return false;
}
template<class T> inline int getidx(vector<T> &v, T a) {
	return lower_bound(all(v), a) - v.begin();
}

constexpr int mod=998244353;
constexpr int inf=3e18;

struct Edge{
	int to,cost,tim;
};
int N,M,S;
vector<Edge>G[50];
int dist[50][2505];
int C[50],D[50];
struct Q{
	int tim,mon,v;
	bool operator<(const Q &a)const{return tim>a.tim;}
	bool operator>(const Q &a)const{return tim<a.tim;}
};
signed main(){
	cin.tie(0);ios::sync_with_stdio(false);
	cin>>N>>M>>S;
	rep(i,M){
		int a,b,c,d;cin>>a>>b>>c>>d;a--;b--;
		G[a].push_back({b,c,d});
		G[b].push_back({a,c,d});
	}
	rep(i,N){
		cin>>C[i]>>D[i];
	}
	rep(i,N)rep(j,2501)dist[i][j]=inf;
	dist[0][min(S,2500ll)]=0;
	priority_queue<Q>que;
	que.push({0,min(S,2500ll),0});
	while(!que.empty()){
		Q p=que.top();que.pop();
		if(dist[p.v][p.mon]<p.tim)continue;
		if(dist[p.v][min(2500ll,p.mon+C[p.v])]>p.tim+D[p.v]){
			dist[p.v][min(2500ll,p.mon+C[p.v])]=p.tim+D[p.v];
			que.push({dist[p.v][min(2500ll,p.mon+C[p.v])],min(2500ll,p.mon+C[p.v]),p.v});
		}
		for(Edge e:G[p.v]){
			if(e.cost>p.mon)continue;
			if(dist[e.to][p.mon-e.cost]>p.tim+e.tim){
				dist[e.to][p.mon-e.cost]=p.tim+e.tim;
				que.push({dist[e.to][p.mon-e.cost],p.mon-e.cost,e.to});
			}
		}
	}
	REP(i,N){
		int ans=inf;
		rep(j,2501)chmin(ans,dist[i][j]);
		cout<<ans<<endl;
	}
}
