#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
#include <cmath>
#include <stack>
#include <iomanip>
#include <tuple>
#include <functional>
#include <cfloat>
#include <map>
#include <set>
#include <array>
#include <stdio.h>
#include <string.h>
using ll = long long;
using namespace std;
//LLONG_MAX = 90^18
#define int long long
#define CONTAINS(v,n) (find((v).begin(), (v).end(), (n)) != (v).end())
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define ARY_SORT(a, size) sort((a), (a)+(size))
#define REMOVE(v,a) (v.erase(remove((v).begin(), (v).end(), (a)), (v).end()))
#define REVERSE(v) (reverse((v).begin(), (v).end()))
#define ARY_REVERSE(v,a) (reverse((v), (v)+(a)))
#define LOWER_BOUND(v,a) (lower_bound((v).begin(), (v).end(), (a)))
#define UPPER_BOUND(v,a) (upper_bound((v).begin(), (v).end(), (a)))
#define REP(i, n) for (int (i)=0; (i) < (n); (i)++)
#define CONTAINS_MAP(m, a) (m).find((a)) != m.end()
void YesNo(bool b) { cout << (b ? "Yes" : "No"); }
void Yes() { cout << "Yes"; }
void No() { cout << "No"; }

//---------- ダイクストラ pair<index,len> ----------
void dijkstra(int node_size, vector<pair<int, int>>* link, bool* used, int s, int* result)
{
	REP(i, node_size)
	{
		result[i] = INT64_MAX;
		used[i] = false;
	}
	result[s] = 0;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q; //len, index
	q.push(pair<int, int>(0, s));
	while (q.size() > 0)
	{
		int d, p;
		tie(d, p) = q.top();
		q.pop();
		if (used[p]) continue;
		used[p] = true;
		for (pair<int, int>& l : link[p])
		{
			if (result[l.first] > d + l.second)
			{
				result[l.first] = d + l.second;
				q.push(pair<int, int>(d + l.second, l.first));
			}
		}
	}
}


int N, M, S;
vector<int> src_link[51];
int len[51][51];
int cost[51][51];
int C[51];
int D[51];

const int MAX_GINKA = 20000;
const int NODE_SIZE = MAX_GINKA * 51;
vector<pair<int, int>> _link[NODE_SIZE];
bool _used[NODE_SIZE];
int _result[NODE_SIZE];


signed main()
{
	cin >> N >> M >> S;
	REP(i, M)
	{
		int u, v, a, b;
		cin >> u >> v >> a >> b;
		src_link[u].push_back(v);
		src_link[v].push_back(u);
		len[u][v] = b;
		len[v][u] = b;
		cost[u][v] = a;
		cost[v][u] = a;
	}
	REP(i, N)
	{
		cin >> C[i + 1] >> D[i + 1];
	}

	for (int i = 1; i <= N; i++)
	{
		for (int j = 0; j < MAX_GINKA; j++)
		{
			int c = min(MAX_GINKA - 1, j + C[i]);
			int d = D[i];

			int src = i * MAX_GINKA + j;
			int dest = i * MAX_GINKA + c;

			_link[src].push_back(make_pair(dest, d));
		}
	}

	for (int i = 1; i <= N; i++)
	{
		for (int l : src_link[i])
		{
			for (int j = 0; j < MAX_GINKA; j++)
			{
				if (cost[i][l] <= j)
				{
					int src = i * MAX_GINKA + j;
					int dest = l * MAX_GINKA + (j - cost[i][l]);
					_link[src].push_back(make_pair(dest, len[i][l]));
				}
			}
		}
	}


	int node_size = MAX_GINKA * 51;
	int s = min(S, MAX_GINKA - 1);
	dijkstra(node_size, _link, _used, 1 * MAX_GINKA + s, _result);


	int min_len[51] = {};
	for (int i = 1; i <= N; i++)
	{
		min_len[i] = LLONG_MAX;
	}
	for (int i = 1; i <= N; i++)
	{
		for (int j = 0; j < MAX_GINKA; j++)
		{
			int len = _result[i * MAX_GINKA + j];
			if (len < LLONG_MAX)
			{
				min_len[i] = min(len, min_len[i]);
			}
		}
	}

	for (int i = 2; i <= N; i++)
	{
		cout << min_len[i] << endl;
	}
}





Measured memory_bytes: 161408