#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#define linf 9000000000000000000ll


using namespace std;
typedef long long ll;


struct edge
{
	ll to, len, cost;
	edge(ll to, ll len, ll cost) : to(to), len(len), cost(cost) {}
};

const int MAX_N = 50;
const int MAX_M = 100;
const int MAX_A = 2500;

int A[MAX_M], B[MAX_M], C[MAX_N], D[MAX_N];

int n, m, sil;

vector<edge> G[51];
vector<ll> _time[MAX_A + 1], min_time;
vector<int> prev[MAX_A + 1];

void dijkstra(int s)
{
	for (int i = 0; i <= MAX_A; i++)
	{
		_time[i].resize(n, linf);
	}

	min_time.resize(n, linf);
	_time[sil][s] = 0;
	min_time[s] = 0;

	using P = pair<ll, pair<int, int>>; // time, (pos, sil)
	priority_queue<P, vector<P>, greater<P>> Q;
	Q.push({0, {s, sil}});

	while (!Q.empty())
	{
		ll cur_time = Q.top().first;
		int cur_pos = Q.top().second.first;
		int cur_sil = Q.top().second.second;
		Q.pop();


		if (_time[cur_sil][cur_pos] < cur_time) continue;
		if (cur_sil != MAX_A)
		{
			int nx_sil = min(MAX_A, cur_sil + C[cur_pos]);
			ll nx_time = cur_time + D[cur_pos];
			if (_time[nx_sil][cur_pos] > nx_time)
			{
				_time[nx_sil][cur_pos] = nx_time;
				Q.push({nx_time,{cur_pos, nx_sil}});
			}
		}

		for (edge e : G[cur_pos])
		{
			ll nx_time = cur_time + e.len;
			int nx_pos = e.to;
			int nx_sil = cur_sil - e.cost;

			if (nx_sil >= 0 and nx_time < _time[nx_sil][nx_pos])
			{
				_time[nx_sil][nx_pos] = nx_time;
				min_time[nx_pos] = min(min_time[nx_pos], nx_time);
				Q.push({nx_time, {nx_pos, nx_sil}});
			}
		}

	}
}


int main()
{
	std::ios::sync_with_stdio(false);

	cin >> n >> m >> sil;
	sil = min(sil, MAX_A);

	for (int i = 0; i < m; i ++)
	{
		int u,v;
		cin >> u >> v >> A[i] >> B[i];
		u--;
		v--;
		G[u].push_back(edge(v, B[i], A[i]));
		G[v].push_back(edge(u, B[i], A[i]));
	}

	for (int i = 0; i < n; i++)
	{
		cin >> C[i] >> D[i];
	}

	dijkstra(0);

	for (int i = 1; i < n; i++)
		cout << min_time[i] << endl;

	return 0;
}