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
#include<bits/stdc++.h>

using namespace std;

const long long INF = 1ll << 61;
const int MAX = 2500;

struct Node{
  long long time;
  int money;
  int node;
  
  bool operator>(const Node& t) const{
    return time > t.time;
  }
};

int main(){
  int N, M, S;
  cin >> N >> M >> S;
  
  vector<vector<Node>> to(N);
  for(int i = 0; i < M; i++){
    int U, V, A, B;
    cin >> U >> V >> A >> B;
    --U; --V;
    
    to[U].push_back({B, A, V});
    to[V].push_back({B, A, U});
  }
  
  vector<int> C(N), D(N);
  for(int i = 0; i < N; i++) cin >> C[i] >> D[i];
  
  vector<vector<long long>> dp(N, vector<long long>(MAX + 1, INF));
  priority_queue<Node, vector<Node>, greater<Node>> pq;
  
  S = min(S, MAX);
  pq.push({0, S, 0});
  dp[0][S] = 0;
  while(!pq.empty()){
    auto [time, money, node] = pq.top();
    pq.pop();
    
    if(dp[node][money] < time) continue;
    
    for(auto [t, m, next] : to[node]){
      if(money >= m && time + t < dp[next][min(money - m, MAX)]){
        dp[next][min(money - m, MAX)] = time + t;
        pq.push({time + t, min(money - m, MAX), next});
      }
    }
    
    if(money < MAX){
      if(time + D[node] < dp[node][min(money + C[node], MAX)]){
        dp[node][min(money + C[node], MAX)] = time + D[node];
        pq.push({time + D[node], min(money + C[node], MAX), node});
      }
    }
  }
  
  for(int i = 0; i < N; i++){
    for(int j = 0; j < MAX; j++){
      dp[i][j + 1] = min(dp[i][j + 1], dp[i][j]);
    }
  }
  
  for(int i = 1; i < N; i++){
    cout << dp[i][MAX] << endl;
  }
  
  return 0;
}