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
//make sure to make new file!
import java.io.*;
import java.util.*;

public class Main{
   
   public static void main(String[] args)throws IOException{
      BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
      PrintWriter out = new PrintWriter(System.out);
      
      StringTokenizer st = new StringTokenizer(f.readLine());
      
      int n = Integer.parseInt(st.nextToken());
      int m = Integer.parseInt(st.nextToken());
      int sc = Integer.parseInt(st.nextToken());
      
      ArrayList<ArrayList<Edge>> adj = new ArrayList<ArrayList<Edge>>(n+1);
      for(int k = 0; k <= n; k++) adj.add(new ArrayList<Edge>());
      
      for(int k = 0; k < m; k++){
         st = new StringTokenizer(f.readLine());
         
         int a = Integer.parseInt(st.nextToken());
         int b = Integer.parseInt(st.nextToken());
         int c = Integer.parseInt(st.nextToken());          //cost
         long t = Long.parseLong(st.nextToken());          //time
         
         adj.get(a).add(new Edge(b,c,t));
         adj.get(b).add(new Edge(a,c,t));
         
      }
      
      int[] ex = new int[n+1];            //how many silvers coins
      int[] ext = new int[n+1];           //exchange time
      
      for(int k = 1; k <= n; k++){
         st = new StringTokenizer(f.readLine());
         
         ex[k]  = Integer.parseInt(st.nextToken());
         ext[k] = Integer.parseInt(st.nextToken());
      }
      
      int MAX = 2600;
      long[][] dists = new long[n+1][MAX+1];
      for(int k = 0; k <= n; k++) Arrays.fill(dists[k],Long.MAX_VALUE);
      
      dists[1][Math.min(MAX,sc)] = 0L;
      /*
      boolean[] seen = new boolean[n+1][MAX+1];
      seen[1][Math.min(MAX,sc)] = true;
      */
      PriorityQueue<State> pq = new PriorityQueue<State>();
      pq.add(new State(1,sc,0L));
      
      while(!pq.isEmpty()){
         State s = pq.poll();
         
         if(dists[s.node][Math.min(MAX,s.coins)] != s.time) continue;
         
         
         if(s.coins < MAX){
            //exchange once
            if(dists[s.node][Math.min(MAX,s.coins + ex[s.node])] > s.time + ext[s.node]){
               dists[s.node][Math.min(MAX,s.coins + ex[s.node])] = s.time + ext[s.node];
               pq.add(new State(s.node,s.coins+ex[s.node],s.time+ext[s.node]));
            }
            //go to next node
            for(Edge e : adj.get(s.node)){
               if(e.c <= s.coins){
                  if(dists[e.to][s.coins-e.c] > s.time + e.t){
                     dists[e.to][s.coins-e.c] = s.time + e.t;
                     pq.add(new State(e.to,s.coins-e.c,s.time + e.t));
                  }
               }
            }
         } else {
            //go to next node
            for(Edge e : adj.get(s.node)){
               if(dists[e.to][MAX] > s.time + e.t){
                  dists[e.to][MAX] = s.time + e.t;
                  pq.add(new State(e.to,MAX,s.time + e.t));
               }
            }
         }
      }
      
      long[] answer = new long[n+1];
      
      for(int k = 2; k <= n; k++){
         answer[k] = Long.MAX_VALUE;
         
         for(int j = 0; j <= MAX; j++){
            answer[k] = Math.min(answer[k],dists[k][j]);
         }
      }
      
      for(int k = 2; k <= n; k++){
         out.println(answer[k]);
      }
         
         
         
         
         
            
      
      
      
      
      
         
      
      
      
      
      
      
      
      out.close();
   }
   
   public static class State implements Comparable<State>{
      int node;
      int coins;
      long time;
      public State(int a, int b, long c){
         node = a;
         coins = b;
         time = c;
      }
      public int compareTo(State s){
         if(time > s.time) return 1;
         if(time < s.time) return -1;
         return 0;
      }
   }
   
   public static class Edge{
      int to;
      int c;
      long t;
      public Edge(int x, int y, long z){
         to = x;
         c = y;
         t = z;
      }
   }
   
   
      
}