#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,S,s,c[55],dis[55][2505],d[55];
bool vis[55][2505];
struct node{
	int a,b,c;
};
vector<node> G[55];
struct Q{
	int now,val,tim;
	inline bool operator <(const Q &o) const{
		return tim>o.tim;
	}
};
priority_queue<Q> q;
inline void dij(){
	q.push(Q({1,min(S,s),0}));
	while(q.size()){
		Q x=q.top();
		q.pop();
		int now=x.now,val=x.val,tim=x.tim;
		if(vis[now][min(val,s)])
			continue;
		vis[now][min(val,s)]=1;
		dis[now][min(val,s)]=tim;
		for(auto N:G[now]){
			int v=N.a,a=N.b,b=N.c;
			if(val>=a)
				q.push(Q({v,val-a,tim+b}));
		}
		while(val<=s){
			val+=c[now],tim+=d[now];
			for(auto N:G[now]){
				int v=N.a,a=N.b,b=N.c;
				if(val>=a)
					q.push(Q({v,val-a,tim+b}));
			}
		}
	}
}
signed main(){
	scanf("%lld%lld%lld",&n,&m,&S);
	for(int u,v,a,b,i=1;i<=m;++i){
		scanf("%lld%lld%lld%lld",&u,&v,&a,&b);
		G[u].push_back(node({v,a,b}));
		G[v].push_back(node({u,a,b}));
		s+=a;
	}
	for(int i=1;i<=n;++i)
		scanf("%lld%lld",&c[i],&d[i]);
	memset(dis,0x3f,sizeof(dis));
	dij();
	for(int i=2;i<=n;++i){
		int ans=1e18;
		for(int j=0;j<=s;++j)
			ans=min(ans,dis[i][j]);
		printf("%lld\n",ans);
	}
	return 0;
}