#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<set>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<cstdlib>
#include<ctime>
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define rev(i,a,b) for(register int i=a;i>=b;--i)
#define gra(i,u) for(register int i=head[u];i;i=edge[i].nxt)
#define Clear(a) memset(a,0,sizeof(a))
#define yes puts("YES")
#define no puts("NO")
using namespace std;
typedef long long ll;
const int INF(1e9+10);
const ll LLINF(1e18+10);
inline int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')s=s*10+(ch-'0'),ch=getchar();
	return s*w;
}
template<typename T>
inline T Min(T x,T y){return x<y?x:y;}
template<typename T>
inline T Max(T x,T y){return x>y?x:y;}
template<typename T>
inline void Swap(T&x,T&y){T t=x;x=y;y=t;return;}
template<typename T>
inline T Abs(T x){return x<0?-x:x;}

const int MAXN(60);
const int MAXM(110);
const int MAXB(5010);

int n,m,s,c[MAXN],D[MAXN];
bool vis[MAXN][MAXB];

struct E{int to,nxt,cost,money;};
E edge[MAXM<<1];
int head[MAXN],tot;

inline void add_edge(int u,int v,int x,int t)
{
	edge[++tot].nxt=head[u];
	head[u]=tot;
	edge[tot].to=v;
	edge[tot].money=x;
	edge[tot].cost=t;
	return;
}

typedef pair<int,int> P;
typedef pair<int,P> PP;
priority_queue<PP,vector<PP>,greater<PP> >q;
ll d[MAXN][MAXB];

inline void dijkstra()
{
	memset(d,0x7f,sizeof(d));
	d[1][s]=0;
	q.push(make_pair(0,make_pair(-s,1)));
	while(!q.empty())
	{
		PP p=q.top();
		q.pop();
		int x=-p.second.first,u=p.second.second;
		if(vis[u][x]) continue;
		vis[u][x]=true;
		gra(i,u)
		{
			E e=edge[i];
			int cc=x-e.money;
			if(cc<0) continue;
			cc=Min(cc,5000);
			if(d[e.to][cc]>d[u][x]+e.cost)
			{
				d[e.to][cc]=d[u][x]+e.cost;
				q.push(make_pair(d[e.to][cc],make_pair(-cc,e.to)));
			}
		}
	}
	return;
}


int main()
{
	n=read(),m=read(),s=read();
	if(s>5000) s=5000;
	rep(i,1,m)
	{
		int u=read(),v=read(),x=read(),t=read();
		add_edge(u,v,x,t),add_edge(v,u,x,t);
	}
	rep(i,1,n)
	{
		c[i]=read(),D[i]=read();
		add_edge(i,i,-c[i],D[i]);
	}
	dijkstra();
	rep(i,2,n)
	{
		ll ans=d[0][0];
		rep(j,0,5000) ans=Min(ans,d[i][j]);
		printf("%lld\n",ans);
	}
	

	return 0;
}
/*
Date : 2022/
Author :
Start coding at :
finish debugging at :
*/