#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>

#define INF_MONEY (64 * 64)
#define INF_COST (UINT64_C(100000000000) * INF_MONEY * 64 * 2)

int N, M, S;
int U[128], V[128], A[128], B[128];
int C[64], D[64];

int edges_count[64];
int edges_to[64][128];
int edges_cost[64][128];
int edges_money[64][128];

uint64_t cost[64][INF_MONEY + 1];
char kakutei[64][INF_MONEY + 1];

struct status_t {
	int node;
	int money;
	uint64_t cost;
};

struct status_t* Q;
int Qcap = 0;
int Qmax = 0;

void aq(int pos) {
	for (;;) {
		int minpos = pos;
		int i;
		for (i = 1; i <= 2; i++) {
			int cpos = pos * 2 + i;
			if (cpos < Qmax && Q[minpos].cost > Q[cpos].cost) minpos = cpos;
		}
		if (minpos == pos) {
			if (pos == 0) break;
			pos = (pos - 1) / 2;
		} else {
			struct status_t temp = Q[pos];
			Q[pos] = Q[minpos];
			Q[minpos] = temp;
			pos = minpos;
		}
	}
}

void enq(int e_node, int e_money, uint64_t e_cost) {
	if (cost[e_node][e_money] > e_cost) {
		cost[e_node][e_money] = e_cost;
		if (Qmax >= Qcap) {
			Q = realloc(Q, sizeof(*Q) * (Qcap = Qmax + 1));
			if (Q == NULL) exit(3);
		}
		Q[Qmax].node = e_node;
		Q[Qmax].money = e_money;
		Q[Qmax].cost = e_cost;
		Qmax++;
		aq(Qmax - 1);
	}
}

struct status_t deq(void) {
	struct status_t ret;
	if (Qmax <= 0) {
		puts("ERROR: empty queue");
		exit(2);
	}
	ret = Q[0];
	if (Qmax > 1) Q[0] = Q[Qmax - 1];
	Qmax--;
	if (Qmax > 0) aq(0);
	return ret;
}

int add_money(int a, int b) {
	int ret = a + b;
	if (ret > INF_MONEY) ret = INF_MONEY;
	return ret;
}

int main(void) {
	int i, j;
	if (scanf("%d%d%d", &N, &M, &S) != 3) return 1;
	for (i = 0; i < M; i++) {
		if (scanf("%d%d%d%d", &U[i], &V[i], &A[i], &B[i]) != 4) return 1;

		edges_to[U[i]][edges_count[U[i]]] = V[i];
		edges_cost[U[i]][edges_count[U[i]]] = B[i];
		edges_money[U[i]][edges_count[U[i]]] = A[i];
		edges_count[U[i]]++;

		edges_to[V[i]][edges_count[V[i]]] = U[i];
		edges_cost[V[i]][edges_count[V[i]]] = B[i];
		edges_money[V[i]][edges_count[V[i]]] = A[i];
		edges_count[V[i]]++;
	}
	for (i = 1; i <= N; i++) {
		if (scanf("%d%d", &C[i], &D[i]) != 2) return 1;
	}
	for (i = 1; i <= N; i++) {
		for (j = 0; j < INF_MONEY + 1; j++) {
			cost[i][j] = INF_COST;
			kakutei[i][j] = 0;
		}
	}
	enq(1, add_money(S, 0), 0);
	while (Qmax > 0) {
		struct status_t current = deq();
		if (!kakutei[current.node][current.money]) {
			uint64_t ccost = cost[current.node][current.money];
			kakutei[current.node][current.money] = 1;
			/* 金を捨てる */
			if (current.money > 0) {
				enq(current.node, current.money - 1, ccost);
			}
			/* 両替する */
			enq(current.node, add_money(current.money, C[current.node]), ccost + D[current.node]);
			/* 移動する */
			for (i = 0; i < edges_count[current.node]; i++) {
				int emoney = edges_money[current.node][i];
				if (emoney <= current.money) {
					int nnode = edges_to[current.node][i];
					uint64_t ncost = ccost + edges_cost[current.node][i];
					enq(nnode, current.money - emoney, ncost);
				}
			}
		}
	}
#if 0
	for (i = 1; i <= N; i++) {
		for (j = 0; j < 16; j++) {
			printf("%5" PRIu64, cost[i][j]);
		}
		puts("");
	}
#else
	for (i = 2; i <= N; i++) {
		printf("%" PRIu64 "\n", cost[i][0]);
	}
#endif
	return 0;
}


Measured memory_bytes: 5264