#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
ll read(){
	ll a=0,b=getchar(),c=1;
	while(!isdigit(b))c=b=='-'?-1:1,b=getchar();
	while(isdigit(b))a=a*10+b-'0',b=getchar();
	return a*c;
}
const ll inf=1LL<<60;
ll n,V;
ll gg(pii p){
    return p.first+p.second*n;
}
struct edge{
	ll to, cost;
};
vector<vector<edge> > g;
vector<ll> d;
void gao(ll s){
    priority_queue<pii,vector<pii>,greater<pii> > q;
    d=vector<ll>(V,inf);
    d[s]=0;
    q.push(pii(0,s));
    while(!q.empty()){
        pii p=q.top();q.pop();
        ll v=p.second;
        if(d[v]<p.first)continue;
		for(int i=0;i<g[v].size();i++){
			edge e=g[v][i];
            if(d[e.to]>d[v]+e.cost){
                d[e.to]=d[v]+e.cost;
                q.push(pii(d[e.to],e.to));
            }
        }
    }
}
int main(){
	n=read();
    ll m=read(),s=read();
    s=min(s,5000LL);
    V=n*6001;
    g=vector<vector<edge> >(n*6001);
    for(int i=0;i<m;i++){
        ll u=read()-1,v=read()-1,a=read(),b=read();
        for(int j=a;j<6001;j++){
            g[gg({u,j})].push_back({gg({v,j-a}),b});
            g[gg({v,j})].push_back({gg({u,j-a}),b});
        }
    }
    for(int i=0;i<n;i++){
        ll c=read(),d=read();
        for(int j=0;j<6001-c;j++)
            g[gg({i,j})].push_back({gg({i,j+c}),d});
    }
    gao(gg({0,s}));
    for(int i=1;i<n;i++){
        ll ans=inf;
        for(int j=0;j<6001;j++)
            ans=min(ans,d[gg({i,j})]);
        cout << ans << endl;
    }
	return 0;
}