#include <stdio.h>
#include <algorithm>
using namespace std;

const int coin = 2555;
long long t[55][coin + 1];
int N, M, S, X[111], Y[111], A[111], B[111], C[55], D[55];

int main()
{
	scanf ("%d %d %d", &N, &M, &S);
	if (S > coin) S = coin;

	for (int i = 1; i <= M; i++) scanf ("%d %d %d %d", &X[i], &Y[i], &A[i], &B[i]);
	for (int i = 1; i <= N; i++) scanf ("%d %d", &C[i], &D[i]);

	for (int i = 1; i <= N; i++) for (int j = 0; j <= coin; j++) t[i][j] = 1e18;
	t[1][S] = 0;

	for (int k = 0; k < N * N; k++){
		for (int i = 1; i <= N; i++) for (int j = 0; j <= coin; j++){
			int k = j + C[i];
			if (k > coin) k = coin;
			t[i][k] = min(t[i][k], t[i][j] + D[i]);
		}

		for (int i = 1; i <= M; i++){
			for (int j = A[i]; j <= coin; j++){
				int k = j - A[i];
				t[X[i]][k] = min(t[X[i]][k], t[Y[i]][j] + B[i]);
				t[Y[i]][k] = min(t[Y[i]][k], t[X[i]][j] + B[i]);
			}
		}
	}

	for (int i = 2; i <= N; i++){
		long long ans = 1e18;
		for (int j = 0; j <= coin; j++) ans = min(ans, t[i][j]);
		printf ("%lld\n", ans);
	}

	return 0;
}