#include <bits/stdc++.h>
#define rep(i,n) for (ll i = 0; i < n; ++i)
using namespace std;
using ll = long long;
using ull = long long unsigned;
using P = pair<ll,ll>;
const ll INF=1001001001;
typedef tuple<int,int,int> T;

class edge {
public:
    ll to;
    ll cost;
		ll time;
		edge(){}
    edge(ll t, ll c, ll d) {
        to = t;
        cost = c;
				time= d;
    }
};




int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll n,m,s;
	cin>>n>>m>>s;
	vector<vector<edge>> G(n);
	vector<vector<edge>> C(n);

	vector<vector<ll>> dist(n,vector<ll> (2500));


//	P G1(n);

//	P C1(n);
	rep(i,m){
		int u1,v1,a2,b2;
		cin>>u1>>v1>>a2>>b2;
		u1--;v1--;
	//	G1[i]=make_pair(u1,v1);
	//	C1[i]=make_pair(a2,b2);
		G[u1].push_back(edge(v1,a2,b2));
		G[v1].push_back(edge(u1,a2,b2));
	//	C[u1].push_back(edge(v1,b2));
	//	G[v1].push_back(edge(u1,b2));
	}


	vector<P> F(n);
	rep(i,n){
		ll c1,d1;
		cin>>c1>>d1;
		F[i]=make_pair(c1,d1);
	}

	rep(i,n)rep(j,2500) dist[i][j] = INF;
	priority_queue<T, vector<T>, greater<T>> que;
//	que.push(T(0,0,0));
	//dist[0][0]=0;
	if (s>2500)s=2500;

		dist[0][s] = 0;

		que.push(T(0,0,s));

//cost, to[1][],to[][1]
	while (!que.empty()) {
		T tnow=que.top();
		que.pop();
		ll c1,a1,b1;
	//	cout<<c1<<' '<<a1<<' '<<b1<<endl;
		tie(c1,a1,b1)=tnow;
		if (dist[a1][b1] < c1) continue;

//上に伸ばす

			ll cnow=F[a1].first;
			ll dnow=F[a1].second;
		//	cout<<cnow<<' '<<dnow<<endl;
	//		rep(j,cnow+1){
			//	cout<<j<<'j'<<endl;
			ll temp=b1+cnow;
				if (temp>2500) temp=2500;

					if (dist[a1][temp]>dist[a1][b1]+dnow){
						dist[a1][temp]=dist[a1][b1]+dnow;
						que.push(T(dist[a1][temp], a1,temp));

					}
		//	}


//横に伸ばす


			for (edge e : G[a1]) {
			//	cout<<e.time<<'t'<<e.cost<<'c'<<e.to<<"to"<<b1<<'b'<<endl;
				if (b1>=e.cost){
					if (dist[e.to][b1-e.cost] > dist[a1][b1] + e.time) {
							dist[e.to][b1-e.cost] = dist[a1][b1] + e.time;
							que.push(T(dist[e.to][b1-e.cost], e.to,b1-e.cost));
					}
			}
		}



	}

rep(i,n-1){
	ll ans=INF;
	rep(j,2500){
		ans=min(ans,dist[i+1][j]);
	}
	cout<<ans<<endl;


}

//cout<<ans;




}
