// Slower C++ solution:
#include <cstdio>

#include <cstring>

#include <iostream>

#include <string>

#include <cmath>

#include <bitset>

#include <vector>

#include <map>

#include <set>

#include <queue>

#include <deque>

#include <algorithm>

#include <complex>

#include <unordered_map>

#include <unordered_set>

#include <random>

#include <cassert>

#include <fstream>

#include <utility>

#include <functional>

#include <time.h>

#include <stack>

#include <array>

#define popcount __builtin_popcount

using namespace std;

typedef long long int ll;

typedef pair<int, int> P;



int main()

{

	int n, m, s;

	cin>>n>>m>>s;

	vector<P> g[51];

	int a[101]; ll b[101];

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

		int u, v; cin>>u>>v>>a[i]>>b[i];

		u--; v--;

		g[u].push_back({v, i});

		g[v].push_back({u, i});

	}

	int c[55]; ll d[55];

	for(int i=0; i<n; i++) cin>>c[i]>>d[i];

	ll dp[51][2525];

	const int mx=2500;

	s=min(s, mx);

	const ll INF=1e18;

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

		for(int j=0; j<=mx; j++){

			dp[i][j]=INF;

		}

	}

	using Pl=pair<ll, P>;

	priority_queue<Pl, vector<Pl>, greater<Pl>> que;

	dp[0][s]=0;

	que.push({0, {0, s}});

	while(!que.empty()){

		auto p=que.top(); que.pop();

		int x=p.second.first, y=p.second.second;

		if(p.first>dp[x][y]) continue;

		int y1=min(mx, y+c[x]);

		if(dp[x][y1]>dp[x][y]+d[x]){

			dp[x][y1]=dp[x][y]+d[x];

			que.push({dp[x][y1], {x, y1}});

		}

		for(auto q:g[x]){

			int x1=q.first, k=q.second;

			if(y<a[k]) continue;

			if(dp[x1][y-a[k]]>dp[x][y]+b[k]){

				dp[x1][y-a[k]]=dp[x][y]+b[k];

				que.push({dp[x1][y-a[k]], {x1, y-a[k]}});

			}

		}

	}

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

		ll ans=INF;

		for(int j=0; j<=mx; j++){

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

		}

		cout<<ans<<endl;

	}

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.684691895800147x):
#include <cstdio>

#include <cstring>

#include <iostream>

#include <string>

#include <cmath>

#include <bitset>

#include <vector>

#include <map>

#include <set>

#include <queue>

#include <deque>

#include <algorithm>

#include <complex>

#include <unordered_map>

#include <unordered_set>

#include <random>

#include <cassert>

#include <fstream>

#include <utility>

#include <functional>

#include <time.h>

#include <stack>

#include <array>

#define popcount __builtin_popcount

using namespace std;

typedef long long int ll;

typedef pair<int, int> P;

template<typename T> // key

struct RadixHeap{

	vector<pair<ll, T>> v[50];

	ll last;

	int size;

	inline int bsr(ll x){

		if(x==0) return -1;

		else return 63-__builtin_clzll(x);

	}

	RadixHeap():last(0), size(0){}

	bool empty(){

		return size==0;

	}

	void push(ll val, T key){

		size++;

		v[bsr(val^last)+1].push_back({val, key});

	}

	pair<ll, T> pop(){

		size--;

		if(!v[0].empty()){

			auto ret=v[0].back();

			v[0].pop_back();

			return ret;

		}

		int k=1;

		while(v[k].empty()) k++;

		ll minval=v[k][0].first;

		T minkey=v[k][0].second;

		for(auto p:v[k]){

			if(p.first<minval){

				minval=p.first;

				minkey=p.second;

			}

		}

		last=minval;

		bool myon=1;

		for(auto p:v[k]){

			if(myon && p.first==minval && p.second==minkey){

				myon=0;

				continue;

			}

			v[bsr(p.first^last)+1].push_back(p);

		}

		v[k].clear();

		return make_pair(minval, minkey);

	}

};

int main()

{

	int n, m, s;

	cin>>n>>m>>s;

	vector<P> g[51];

	int a[101]; ll b[101];

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

		int u, v; cin>>u>>v>>a[i]>>b[i];

		u--; v--;

		g[u].push_back({v, i});

		g[v].push_back({u, i});

	}

	int c[55]; ll d[55];

	for(int i=0; i<n; i++) cin>>c[i]>>d[i];

	ll dp[51][2525];

	const int mx=2500;

	s=min(s, mx);

	const ll INF=1e18;

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

		for(int j=0; j<=mx; j++){

			dp[i][j]=INF;

		}

	}

	RadixHeap<P> que;

	dp[0][s]=0;

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

	while(!que.empty()){

		auto p=que.pop();

		int x=p.second.first, y=p.second.second;

		if(p.first>dp[x][y]) continue;

		int y1=min(mx, y+c[x]);

		if(dp[x][y1]>dp[x][y]+d[x]){

			dp[x][y1]=dp[x][y]+d[x];

			que.push(dp[x][y1], P(x, y1));

		}

		for(auto q:g[x]){

			int x1=q.first, k=q.second;

			if(y<a[k]) continue;

			if(dp[x1][y-a[k]]>dp[x][y]+b[k]){

				dp[x1][y-a[k]]=dp[x][y]+b[k];

				que.push(dp[x1][y-a[k]], P(x1, y-a[k]));

			}

		}

	}

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

		ll ans=INF;

		for(int j=0; j<=mx; j++){

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

		}

		cout<<ans<<endl;

	}

	return 0;

}