#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#define int long long
using namespace std;
const int maxn = 110;

int read(){
	int x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+c-48;c=getchar();}
	return x*f;
}

int to[maxn<<1],net[maxn<<1],h[maxn],w[maxn<<1],cost[maxn<<1],e=1;
inline void add(int x,int y,int C,int z){
	to[++e]=y;net[e]=h[x];h[x]=e;w[e]=z;cost[e]=C;
}

int k,m,n;
struct node{
	int u,v,a,b;
}p[maxn];	
int c[maxn],d[maxn];
int dp[51][2501],max_=2500;
queue<pair<int,int> > q;
signed main(){
	n=read();m=read();int s=read();
	for(register int i=1;i<=m;i++){
		p[i].u=read();p[i].v=read();p[i].a=read();p[i].b=read();
		add(p[i].u,p[i].v,p[i].a,p[i].b);
		add(p[i].v,p[i].u,p[i].a,p[i].b);
	}
	for(register int i=1;i<=n;i++){
		c[i]=read();d[i]=read();
	}
	memset(dp,0x3f,sizeof(dp));
	for(register int i=0;i<=min(s,max_);i++)dp[1][i]=0;
	for(register int i=s+1;i<=max_;i++){
		int x=max(i-c[1],0ll);
		dp[1][i]=dp[1][x]+d[1];
	}
	for(register int i=0;i<=max_;i++)q.push(make_pair(1,i));
	while(!q.empty()){
		int x=q.front().first,now=q.front().second;q.pop();
		//cout<<x<<" "<<now<<" "<<dp[x][now]<<endl;
		for(register int i=1;i*c[x]+now<=max_;i++){
			if(dp[x][i*c[x]+now]>dp[x][now]+i*d[x]){
				dp[x][i*c[x]+now]=dp[x][now]+i*d[x];
				q.push(make_pair(x,i*c[x]+now));
			}
		}
		for(register int i=h[x];i;i=net[i]){
			int y=to[i];
			if(cost[i]>now)continue;
			if(dp[y][now-cost[i]]>dp[x][now]+w[i]){
				dp[y][now-cost[i]]=dp[x][now]+w[i];
				q.push(make_pair(y,now-cost[i]));
			}
		}
	}
	for(register int i=2;i<=n;i++){
		int min_=1e15;
		for(register int j=0;j<=max_;j++)min_=min(min_,dp[i][j]);
		printf("%lld\n",min_);
	}
	return 0;
}