//#include<bits\stdc++.h>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<string>
#include<ctime>
#include<cmath>
#include<cctype>
#include<cstdlib>
#include<queue>
#include<deque>
#include<stack>
#include<vector>
#include<algorithm>
#include<utility>
#include<bitset>
#include<set>
#include<map>
#define ll long long
#define db double
#define INF 1000000000
#define ldb long double
#define pb push_back
#define get(x) x=read()
#define gt(x) scanf("%d",&x)
#define gi(x) scanf("%lf",&x)
#define put(x) printf("%d\n",x)
#define putl(x) printf("%lld\n",x)
#define gc(a) scanf("%s",a+1)
#define rep(p,n,i) for(RE ll i=p;i<=n;++i)
#define go(x) for(ll i=lin[x],tn=ver[i];i;tn=ver[i=nex[i]])
#define fep(n,p,i) for(RE ll i=n;i>=p;--i)
#define pii pair<ll,ll>
#define mk make_pair
#define RE register
#define P 1000000007
#define mod 998244353
#define S second 
#define F first
#define gf(x) scanf("%lf",&x)
#define pf(x) ((x)*(x))
#define ull unsigned long long
#define ui unsigned
#define zz p<<1
#define yy p<<1|1
using namespace std;
char buf[1<<15],*fs,*ft;
inline char getc()
{
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;
}
inline ll read()
{
    register ll x=0,f=1;register char ch=getc();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();}
    return x*f;
}
const ll MAXN=250;
ll n,m,S,cnt,len;
ll w[MAXN],vis[MAXN],c[MAXN],ans[MAXN];
ll lin[MAXN],ver[MAXN],nex[MAXN],e[MAXN],e1[MAXN];
struct wy
{
	ll x,v,s;
	ll friend operator < (wy a,wy b){return a.v>b.v;}
};
inline void add(ll x,ll y,ll z,ll z1)
{
	ver[++len]=y;
	nex[len]=lin[x];
	lin[x]=len;
	e[len]=z;
	e1[len]=z1;
}
priority_queue<wy>q;
inline void dij()
{
	q.push((wy){1,0,S});
	vis[1]=1;
	while(q.size())
	{
		wy cc=q.top();
		q.pop();
		if(!vis[cc.x])vis[cc.x]=cc.v,--cnt;
		if(!cnt)return;
		q.push((wy){cc.x,cc.v+w[cc.x],cc.s+c[cc.x]});
		go(cc.x)
		{
			if(cc.s>=e1[i])q.push((wy){tn,cc.v+e[i],cc.s-e1[i]});
		}
	}
}
signed main()
{
	//freopen("1.in","r",stdin);
	get(n);get(m);get(S);cnt=n-1;
	rep(1,m,i)
	{
		ll get(x),get(y),get(z1),get(z);
		add(x,y,z,z1);add(y,x,z,z1);
	}
	rep(1,n,i)get(c[i]),get(w[i]);
	dij();
	rep(2,n,i)putl(vis[i]);
	return 0;
}
