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 java.util.stream.*;
import java.io.*;

class Edge implements Comparable<Edge> {

  int to;
  int fee;
  long time;

  Edge(int to, int fee, long time){
    this.to = to;
    this.fee = fee;
    this.time = time;
  }

  @Override
  public int compareTo(Edge o) {
    if(time > o.time) return 1;
    if(time < o.time) return -1;
    return 0;
  }

}

class Graph {
  public ArrayList<Edge>[] adjacency;

  Graph(int n){
    adjacency = new ArrayList[n];
    for(int i = 0; i < n; i++){
      adjacency[i] = new ArrayList<Edge>();
    }
  }

  public void add_edge(int from, int to, int fee, int time){
    adjacency[from].add(new Edge(to, fee, time));
    adjacency[to].add(new Edge(from, fee, time));        
  }
}

public class Main {

  static int n, m, s, maxFee;
  static int[] c, d;
  static long[] ans;
  static long[][] dp;

  static final long INFL = 0xfffffffffffffffL;

  static Graph g;
  
  public static void main(String[] args) throws Exception {
    
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    String[] in = br.readLine().split(" ");
    n = Integer.parseInt(in[0]);
    m = Integer.parseInt(in[1]);
    s = Integer.parseInt(in[2]);

    g = new Graph(n);

    int[] a;
    for(int i = 0; i < m; i++){
      in = br.readLine().split(" ");
      a = Stream.of(in).mapToInt(Integer::parseInt).toArray();
      g.add_edge(a[0]-1, a[1]-1, a[2], a[3]);
    }

    c = new int[n];
    d = new int[n];

    for(int i = 0; i < n; i++){
      in = br.readLine().split(" ");
      c[i] = Integer.parseInt(in[0]);
      d[i] = Integer.parseInt(in[1]);
    }
    
    br.close();

    maxFee = (n-1) * 50;
    s = Math.min(maxFee, s);

    dp = new long[n][2525];

    for(int i = 0; i < n; i++){
      Arrays.fill(dp[i], INFL);
    }

    PriorityQueue<Edge> pq = new PriorityQueue<>();
    pq.add(new Edge(0, s, 0));

    while(!pq.isEmpty()){
      Edge e = pq.poll();
      if(dp[e.to][e.fee] <= e.time) continue;

      for(int i = e.fee; i >= 0 && dp[e.to][i] > e.time; i--){
        dp[e.to][i] = e.time;
      }

      int nextFee = Math.min(e.fee + c[e.to], maxFee);
      pq.add(new Edge(e.to, nextFee, e.time + d[e.to]));
      for(Edge nextEdge : g.adjacency[e.to]){
        if(nextEdge.fee > e.fee) continue;
        pq.add(new Edge(nextEdge.to, e.fee - nextEdge.fee, e.time + nextEdge.time));
      }
    }

    for(int i = 1; i < n; i++){
      System.out.println(dp[i][0]);
    }
    
  }

}