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
//--- pE ---//
import java.util.*;
import java.lang.*;
import java.io.*;
public class Main {
	public static void main (String[] args) throws java.lang.Exception {
		new Solution();
	}
}
class Solution {
	Reader reader;
	PrintWriter out;
	public Solution() {
		reader = new Reader();
		out = new PrintWriter(System.out);
		while (reader.hasNext()) {
			run_case();
		}
		out.flush();
	}

	private void run_case() {
		int n = reader.ni();
		long m = reader.nl();
		long s = reader.nl();

		Map<Integer, Map<Integer, Cost>> adj = new HashMap<>();

		long inf = Long.MAX_VALUE;

		for (int i=0; i<m; i++) {
			int u = reader.ni();
			int v = reader.ni();
			long a = reader.nl();
			long b = reader.nl();
			Cost cst = new Cost(a, b);
			adj.putIfAbsent(u, new HashMap<>());
			adj.get(u).put(v, cst);
			adj.putIfAbsent(v, new HashMap<>());
			adj.get(v).put(u, cst);
		}

		long[] time_cost = new long[n+1];
		long[] change = new long[n+1];
		for (int i=1; i<=n; i++) {
			long c = reader.nl();
			long d = reader.nl();
			change[i] = c;
			time_cost[i] = d;
		}

		PriorityQueue<State> pq = new PriorityQueue<>(new ComparatorState());
		pq.offer(new State(1, (long)0, s));

		long[] res = new long[n+1];
		Arrays.fill(res, inf);
		int found_cnt = 0;

		long[] max_silver = new long[n+1];
		Arrays.fill(max_silver, -1);

		while (!pq.isEmpty()) {
			State cur = pq.poll();

			if (res[cur.node] == inf) found_cnt ++;
			res[cur.node] = Math.min(res[cur.node], cur.time);
			if (found_cnt == n) break;

			if (max_silver[cur.node] >= cur.silver) continue;
			max_silver[cur.node] = Math.max(max_silver[cur.node], cur.silver);

			List<Long> need = new ArrayList<>();

			if (adj.get(cur.node) != null) {
				for (int nx : adj.get(cur.node).keySet()) {
					Cost t = adj.get(cur.node).get(nx);
					if (cur.silver < t.coin) {
						long left = t.coin - cur.silver;
						long need_round = (long)Math.ceil(1.0 * left / change[cur.node]);
						pq.offer(new State(cur.node, cur.time + time_cost[cur.node] * need_round, cur.silver + change[cur.node] * need_round));
					} else {
						pq.offer(new State(nx, cur.time + t.time, cur.silver - t.coin));
					}
				}
			}

			pq.offer(new State(cur.node, cur.time + time_cost[cur.node], cur.silver + change[cur.node]));
		}

		for (int i=2; i<=n; i++) out.println(res[i]);

		return;
	}

}
class Cost {
	public long time, coin;
	public Cost(long coin, long time) {
		this.time = time;
		this.coin = coin;
	}
}

class State {
	public int node;
	public long time, silver;
	public State(int node, long time, long silver) {
		this.node = node;
		this.time = time;
		this.silver = silver;
	}
}

class ComparatorState implements Comparator<State> {
	public int compare(State a, State b) {
		if (a.time == b.time) {
			if (a.silver < b.silver) {
				return 1;
			} else if (a.silver == b.silver) {
				return 0;
			} else {
				return -1;
			}
			// return b.silver - a.silver;
		}
		if (a.time > b.time) {
			return 1;
		} else if (a.time == b.time) {
			return 0;
		} else {
			return -1;
		}
		// return a.time - b.time;
	}
}

class Reader {
	BufferedReader br;
	StringTokenizer st;
	public Reader(){
		try {
			br = new BufferedReader(new InputStreamReader(System.in));
			st = new StringTokenizer(br.readLine());
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	public String next() {
		if (st.hasMoreTokens()) return st.nextToken();
		try {
			st = new StringTokenizer(br.readLine());
		} catch (Exception e) {
			e.printStackTrace();
		}
		return st.nextToken();
	}
	public boolean hasNext() {
		try {
			if (!st.hasMoreTokens() && !br.ready()) return false;
			else return true;
		} catch (Exception e) {
			e.printStackTrace();
		}
		return false;
	}
	public int ni() {return Integer.parseInt(this.next());}
	public long nl() {return Long.parseLong(this.next());}
	public String ns() {return this.next();}
}
