// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;



#define fi first

#define se second

#define eb emplace_back

#define mt make_tuple

#define all(x) (x).begin(), (x).end() 

#define MOD 1000000007



typedef long long ll;

typedef pair <int, int> ii;

typedef pair <ll, ll> pll;

typedef vector<int> vi;

typedef vector<ll> vll;

typedef long double ld;



const ll INF=LLONG_MAX;

const int mxn=55;

using T = tuple<int,ll,ll>;

int n,m,s;

ll ctr[mxn],tsct[mxn],dist[mxn][5005];

vector<T>adj[mxn];



struct state{

	int u; ll c,t;

	state(int u, ll c, ll t):u(u),c(c),t(t){};

	bool operator>(const state &s)const{return t>s.t;}

};



void dij(){

	for(int i=0; i<n; i++)

		for(int j=0; j<5005; j++)

			dist[i][j]=INF;

	

	priority_queue<state,vector<state>,greater<state>>pq;

	dist[0][s]=0LL;

	pq.push(state(0,s,0));

	while(!pq.empty()){

		state cur = pq.top(); pq.pop();

		for(T x:adj[cur.u]){

			int v; ll c,w;

			tie(v,c,w)=x;

			if(cur.c-c<0)continue;

			if(dist[v][cur.c-c]>dist[cur.u][cur.c]+w){

				dist[v][cur.c-c]=dist[cur.u][cur.c]+w;

				pq.push(state(v,cur.c-c,dist[v][cur.c-c]));

			}

		}

		if(cur.c+ctr[cur.u]<=5000){

			if(dist[cur.u][cur.c+ctr[cur.u]]>dist[cur.u][cur.c]+tsct[cur.u]){

				dist[cur.u][cur.c+ctr[cur.u]]=dist[cur.u][cur.c]+tsct[cur.u];

				pq.push(state(cur.u,cur.c+ctr[cur.u],dist[cur.u][cur.c+ctr[cur.u]]));

			}

		}

	}

}



int main()

{

    ios_base::sync_with_stdio(0); cin.tie(0);

    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);

	cin >> n >> m >> s;

	s=min(s,5000);

	int u,v,a,b;

	for(int i=0; i<m; i++){

		cin >> u >> v >> a >> b;

		u--; v--;

		adj[u].eb(v,a,b);

		adj[v].eb(u,a,b);

	}

	for(int i=0; i<n; i++)cin >> ctr[i] >> tsct[i];

	dij();

	vll ans(n,INF);

	for(int i=1; i<n; i++)

		for(int j=0; j<5005; j++)

			ans[i]=min(ans[i],dist[i][j]);

	for(int i=1; i<n; i++)

		cout << ans[i] << endl;

}

	

// READ & UNDERSTAND

// ll, int overflow, array bounds, memset(0)

// special cases (n=1?), n+1 (1-index)

// do smth instead of nothing & stay organized

// WRITE STUFF DOWN


// Faster C++ solution for the same problem (measured speedup: 1.624785759468297x):
#include <bits/stdc++.h>



using namespace std;



#define fi first

#define se second

#define eb emplace_back

#define mt make_tuple

#define all(x) (x).begin(), (x).end() 

#define MOD 1000000007



typedef long long ll;

typedef pair <int, int> ii;

typedef pair <ll, ll> pll;

typedef vector<int> vi;

typedef vector<ll> vll;

typedef long double ld;



const ll INF=LLONG_MAX;

const int mxn=55;

using T = tuple<int,ll,ll>;

int n,m,s;

ll ctr[mxn],tsct[mxn],dist[mxn][2505];

vector<T>adj[mxn];



struct state{

	int u; ll c,t;

	state(int u, ll c, ll t):u(u),c(c),t(t){};

	bool operator>(const state &s)const{return t>s.t;}

};



void dij(){

	for(int i=0; i<n; i++)

		for(int j=0; j<2505; j++)

			dist[i][j]=INF;

	

	priority_queue<state,vector<state>,greater<state>>pq;

	dist[0][s]=0LL;

	pq.push(state(0,s,0));

	while(!pq.empty()){

		state cur = pq.top(); pq.pop();

		for(T x:adj[cur.u]){

			int v; ll c,w;

			tie(v,c,w)=x;

			if(cur.c-c<0)continue;

			if(dist[v][cur.c-c]>dist[cur.u][cur.c]+w){

				dist[v][cur.c-c]=dist[cur.u][cur.c]+w;

				pq.push(state(v,cur.c-c,dist[v][cur.c-c]));

			}

		}

		if(cur.c+ctr[cur.u]<=2500){

			if(dist[cur.u][cur.c+ctr[cur.u]]>dist[cur.u][cur.c]+tsct[cur.u]){

				dist[cur.u][cur.c+ctr[cur.u]]=dist[cur.u][cur.c]+tsct[cur.u];

				pq.push(state(cur.u,cur.c+ctr[cur.u],dist[cur.u][cur.c+ctr[cur.u]]));

			}

		}

	}

}



int main()

{

    ios_base::sync_with_stdio(0); cin.tie(0);

    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);

	cin >> n >> m >> s;

	s=min(s,2500);

	int u,v,a,b;

	for(int i=0; i<m; i++){

		cin >> u >> v >> a >> b;

		u--; v--;

		adj[u].eb(v,a,b);

		adj[v].eb(u,a,b);

	}

	for(int i=0; i<n; i++)cin >> ctr[i] >> tsct[i];

	dij();

	vll ans(n,INF);

	for(int i=1; i<n; i++)

		for(int j=0; j<2505; j++)

			ans[i]=min(ans[i],dist[i][j]);

	for(int i=1; i<n; i++)

		cout << ans[i] << endl;

}

	

// READ & UNDERSTAND

// ll, int overflow, array bounds, memset(0)

// special cases (n=1?), n+1 (1-index)

// do smth instead of nothing & stay organized

// WRITE STUFF DOWN