There are N cities numbered 1 to N, connected by M railroads.

You are now at City 1, with 10^{100} gold coins and S silver coins in your pocket.

The i-th railroad connects City U_i and City V_i bidirectionally, and a one-way trip costs A_i silver coins and takes B_i minutes. You cannot use gold coins to pay the fare.

There is an exchange counter in each city. At the exchange counter in City i, you can get C_i silver coins for 1 gold coin. The transaction takes D_i minutes for each gold coin you give. You can exchange any number of gold coins at each exchange counter.

For each t=2, ..., N, find the minimum time needed to travel from City 1 to City t. You can ignore the time spent waiting for trains.

Constraints

* 2 \leq N \leq 50
* N-1 \leq M \leq 100
* 0 \leq S \leq 10^9
* 1 \leq A_i \leq 50
* 1 \leq B_i,C_i,D_i \leq 10^9
* 1 \leq U_i < V_i \leq N
* There is no pair i, j(i \neq j) such that (U_i,V_i)=(U_j,V_j).
* Each city t=2,...,N can be reached from City 1 with some number of railroads.
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N M S
U_1 V_1 A_1 B_1
:
U_M V_M A_M B_M
C_1 D_1
:
C_N D_N


Output

For each t=2, ..., N in this order, print a line containing the minimum time needed to travel from City 1 to City t.

Examples

Input

3 2 1
1 2 1 2
1 3 2 4
1 11
1 2
2 5


Output

2
14


Input

4 4 1
1 2 1 5
1 3 4 4
2 4 2 2
3 4 1 1
3 1
3 1
5 2
6 4


Output

5
5
7


Input

6 5 1
1 2 1 1
1 3 2 1
2 4 5 1
3 5 11 1
1 6 50 1
1 10000
1 3000
1 700
1 100
1 1
100 1


Output

1
9003
14606
16510
16576


Input

4 6 1000000000
1 2 50 1
1 3 50 5
1 4 50 7
2 3 50 2
2 4 50 4
3 4 50 3
10 2
4 4
5 5
7 7


Output

1
3
5


Input

2 1 0
1 2 1 1
1 1000000000
1 1


Output

1000000001
// practice with kaiboy
import java.io.*;
import java.util.*;

public class Main extends PrintWriter {
	Main() { super(System.out); }
	Scanner sc = new Scanner(System.in);
	public static void main(String[] $) {
		Main o = new Main(); o.main(); o.flush();
	}

	static final long INF = 0x3f3f3f3f3f3f3f3fL;
	static final int A = 50;
	int[] oo; int[][] oh;
	void link(int i, int h) {
		int o = oo[i];
		if (o >= 2 && (o & o - 1) == 0)
			oh[i] = Arrays.copyOf(oh[i], o << 1);
		oh[i][oo[i]++] = h;
	}
	int[] aa, bb, ij;
	void init(int n, int m) {
		oo = new int[n]; oh = new int[n][2];
		aa = new int[m + n]; bb = new int[m + n]; ij = new int[m + n];
	}
	long[] dd; int[] pq, iq; int cnt;
	boolean lt(int i, int j) {
		return dd[i] < dd[j];
	}
	int p2(int p) {
		return (p *= 2) > cnt ? 0 : p < cnt && lt(iq[p + 1], iq[p]) ? p + 1 : p;
	}
	void pq_up(int i) {
		int j, p, q;
		for (p = pq[i]; (q = p / 2) > 0 && lt(i, j = iq[q]); p = q)
			iq[pq[j] = p] = j;
		iq[pq[i] = p] = i;
	}
	void pq_dn(int i) {
		int j, p, q;
		for (p = pq[i]; (q = p2(p)) > 0 && lt(j = iq[q], i); p = q)
			iq[pq[j] = p] = j;
		iq[pq[i] = p] = i;
	}
	void pq_add_last(int i) {
		iq[pq[i] = ++cnt] = i;
	}
	int pq_remove_first() {
		int i = iq[1], j = iq[cnt--];
		if (j != i) {
			pq[j] = 1; pq_dn(j);
		}
		pq[i] = 0;
		return i;
	}
	void main() {
		int n = sc.nextInt();
		int m = sc.nextInt();
		int s = sc.nextInt();
		init(n, m);
		for (int h = 0; h < m; h++) {
			int i = sc.nextInt() - 1;
			int j = sc.nextInt() - 1;
			aa[h] = -sc.nextInt();
			bb[h] = sc.nextInt();
			ij[h] = i ^ j;
			link(i, h);
			link(j, h);
		}
		for (int h = m, i = 0; i < n; h++, i++) {
			aa[h] = sc.nextInt();
			bb[h] = sc.nextInt();
			link(i, h);
		}
		int md = n * A + 1;
		s = Math.min(s, md - 1);
		pq = new int[n * md]; iq = new int[1 + n * md];
		dd = new long[n * md]; Arrays.fill(dd, INF);
		dd[s] = 0; pq_add_last(s);
		while (cnt > 0) {
			int u = pq_remove_first(), i = u / md; s = u % md;
			for (int o = 0; o < oo[i]; o++) {
				int h = oh[i][o], j = i ^ ij[h], t = s + aa[h];
				if (t < 0)
					continue;
				t = Math.min(t, md - 1);
				int v = j * md + t;
				long d = dd[u] + bb[h];
				if (dd[v] > d) {
					if (dd[v] == INF)
						pq_add_last(v);
					dd[v] = d; pq_up(v);
				}
			}
		}
		for (int i = 1; i < n; i++) {
			long d = INF;
			for (s = 0; s < md; s++) {
				int u = i * md + s;
				d = Math.min(d, dd[u]);
			}
			println(d);
		}
	}
}
