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
import java.util.*;
import static java.lang.Math.*;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		
		// 入力
		int n = sc.nextInt();
		int m = sc.nextInt();
		int s = sc.nextInt();
		Graph g = new Graph(n, false);
		int max = 0;
		for(int i = 0; i < m; i++){
		    int from = sc.nextInt()-1;
		    int to = sc.nextInt()-1;
		    int a = sc.nextInt();
		    int b = sc.nextInt();
		    g.add(from, to, a, b);
		    max = max(max, a);
		}
		for(int i = 0; i < n; i++){
		    int c = sc.nextInt();
		    int d = sc.nextInt();
		    g.addCD(i, c, d);
		}
		
		// 計算
		//long result = 0;
		long[] result = g.dijkstra(0, min(s, max*n), max);
		
		// 出力
		for(int i = 1; i < n; i++){
		    System.out.println(result[i]);
		}
		//System.out.println(result);
	}
}

class Graph {
	int n;
	boolean directed;
	ArrayList<Edge>[] adjList;
	int m;
	long[][] dist;
	int start;
	int[] prev;
	long INF = 1001001001001001001L;
	int[] c;
	int[] d;

	public Graph (int n, boolean directed) {
		this.n = n;
		this.m = 0;
		this.directed = directed;
		this.adjList = new ArrayList[n];
		for(int i = 0; i < n; i++){
			adjList[i] = new ArrayList<Edge>();
		}
		this.c = new int[n];
		this.d = new int[n];
	}

	public void add(int from, int to, int a, int w) {
		adjList[from].add(new Edge(from, to, a, w));
		this.m++;
		if(!directed){
			adjList[to].add(new Edge(to, from, a, w));
			this.m++;
		}
	}
	
	public void addCD(int id, int c, int d) {
		this.c[id] = c;
		this.d[id] = d;
	}
	
	public long[] dijkstra(int start, int s, int max) { // O(MlogM)
		this.start = start;
		this.prev = new int[n];
		Arrays.fill(prev, -1);
		prev[start] = start;
		this.dist = new long[n][max*n+1];
		for(int i = 0; i < n; i++){
		    Arrays.fill(dist[i], INF);
		}
		dist[start][s] = 0;
		PriorityQueue<Vertex> q = new PriorityQueue<Vertex>((x, y) -> Long.compare(x.distance, y.distance));
		q.add(new Vertex(start, s, 0));
		while(!q.isEmpty()){
			Vertex now = q.poll();
			if(now.distance != dist[now.id][now.a]) continue;
			
			int charge = min(max*n, now.a + c[now.id]);
			if(dist[now.id][charge] > now.distance + d[now.id]){
			    dist[now.id][charge] = now.distance + d[now.id];
			    q.add(new Vertex(now.id, charge, now.distance + d[now.id]));
			}
			
			for(Edge e : adjList[now.id]){
			    int newA = now.a - e.cost;
			    if(newA < 0) continue;
				long newDist = now.distance + e.w;
				if(dist[e.to][newA] <= newDist) continue;
				dist[e.to][newA] = newDist;
				prev[e.to] = now.id;
				q.add(new Vertex(e.to, newA, newDist));
			}
		}
		return minDist();
	}
	
	public long[] minDist(){
		long[] minDist = new long[n];
		Arrays.fill(minDist, INF);
		for(int i = 0; i < n; i++){
		    for(int j = 0; j < dist[0].length; j++){
		        minDist[i] = min(minDist[i], dist[i][j]);
		    }
		}
		return minDist;
	}
	
	public String toString(){
		StringBuilder sb = new StringBuilder();
		for(ArrayList<Edge> list : adjList){
			for(Edge e : list){
				sb.append(e.toString());
				sb.append("\n");
			}
		}
		return sb.toString();
	}
	
	class Edge {
		int from;
		int to;
		int cost;
		int w;
		
		Edge(int from, int to, int cost, int w){
			this.from = from;
			this.to = to;
			this.cost = cost;
			this.w = w;
		}
		
		public String toString(){
			return "from:" + from + " to:" + to + " cost:" + cost + " w:" + w;
		}
	}
	
	class Vertex {
		int id;
		int a;
		long distance;
		
		Vertex(int id, int a, long distance){
			this.id = id;
			this.a = a;
			this.distance = distance;
		}
		
		public String toString(){
			return "id:" + id + " a:" + a + " distance:" + distance;
		}
	}
}


