#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
#include <numeric>
#include <functional>

using namespace std;
#define ALL(x)              (x).begin(),(x).end()
typedef long long           ll;
#define REP(i, n)           for (ll i = 0 ; i < (ll)n ; ++i)
#define REPN(i, m, n)       for (ll i = m ; i < (ll)n ; ++i)
#define INF                 (ll)2e9
#define MOD                 (1000 * 1000 * 1000 + 7)
#define Ceil(x, n)          (((((x))+((n)-1))/n))
#define CeilN(x, n)         (((((x))+((n)-1))/n)*n)
#define FloorN(x, n)        ((x)-(x)%(n))
#define IsOdd(x)            (((x)&0x01UL) == 0x01UL)
#define IsEven(x)           (!IsOdd((x)))
#define M_PI                3.14159265358979323846
typedef pair<ll, ll>	    P;

/*-----------------------------------------------------------------------------
　処理
 -----------------------------------------------------------------------------*/
// 枝定義
struct Edge
{
	ll to;
	ll silver;
	ll cost;
	Edge(){}
	Edge(ll to, ll silver, ll cost) : to(to), silver(silver), cost(cost){}
};

struct queParam
{
	ll v;
	ll silver;
	ll cost;
	
	queParam(ll v, ll s, ll t) : v(v), silver(s), cost(t){}
	bool operator<(const queParam &a) const {
		return cost > a.cost;
	}
};

// グラフ定義(二次元配列)
template <class E>
using Graph = vector<vector<E>>;

// ダイクストラ
class Dijkstra
{
private:
	const ll maxSilver = 3000;

public:
	// res[i] = sからiまでの最短距離
	vector<vector<ll>> res;

public:
	Dijkstra(const Graph<Edge> &G, const vector<ll> &C, const vector<ll> &D, int s)
	{
		int V = (int)G.size();
		res = vector<vector<ll>>(V, vector<ll>(maxSilver + 1, INF));

		priority_queue<queParam> que;
		que.emplace(0, s, 0);
		res[0][s] = 0;

		while (!que.empty()) {
			queParam qOne = que.top(); que.pop();

			// 違う最短距離がキューにあるのでスキップ
			if (res[qOne.v][qOne.silver] < qOne.cost) {
				continue;
			}
			if (qOne.silver < 0) {
				continue;
			}

			ll nokoriSilver = min(maxSilver, qOne.silver + C[qOne.v]);
			ll koukanCost = qOne.cost + D[qOne.v];
			if (res[qOne.v][nokoriSilver] > koukanCost) {
				res[qOne.v][nokoriSilver] = koukanCost;
				que.emplace(qOne.v, nokoriSilver, koukanCost);
			}

			// 最短距離を更新
			for (Edge e : G[qOne.v]) {
				nokoriSilver = qOne.silver - e.silver;
				if (0 <= nokoriSilver) {
					ll &nowCost = res[e.to][nokoriSilver];
					ll newCost = res[qOne.v][qOne.silver] + e.cost;
					if (nowCost > newCost) {
						nowCost = newCost;
						que.emplace(e.to, nokoriSilver, newCost);
					}
				}
			}
		}
	}
};

int main()
{
	int N, M, S;
	cin >> N >> M >> S;
	Graph<Edge>	G(N);
	REP(i, M) {
		ll u, v, a, b;
		cin >> u >> v >> a >> b;
		u--, v--;
		G[u].emplace_back(Edge(v, a, b));
		G[v].emplace_back(Edge(u, a, b));
	}

	vector<ll> C(N), D(N);
	REP(i, N) {
		cin >> C[i] >> D[i];
	}

	Dijkstra dijk(G, C, D, S);

	REPN(i, 1, N) {
		ll ans = INF;
		for (auto one : dijk.res[i]) {
			ans = min(ans, one);
		}
		cout << ans << endl;
	}

	return 0;
}
