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.*;

class Edge {
    public int v;
    public int A;
    public int B;

    public Edge(int v, int a, int b) {
        this.v = v;
        A = a;
        B = b;
    }
}

class Node implements Comparable<Node> {
    public int u;
    public int coin;
    public long time;

    public Node(int u, int coin, long time) {
        this.u = u;
        this.coin = coin;
        this.time = time;
    }

    @Override
    public int compareTo(Node node) {
        return Long.compare(time, node.time);
    }
}

public class Main {
    private static final Scanner sc = new Scanner(System.in);

    private void solve() {
        int N = sc.nextInt();
        int M = sc.nextInt();
        int S = sc.nextInt();

        List<List<Edge>> adj = new ArrayList<>();
        for (int i = 0; i < N + 1; ++i) {
            adj.add(new ArrayList<>());
        }
        for (int i = 0; i < M; ++i) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int A = sc.nextInt();
            int B = sc.nextInt();
            adj.get(u).add(new Edge(v, A, B));
            adj.get(v).add(new Edge(u, A, B));
        }

        int[] c = new int[N + 1];
        int[] d = new int[N + 1];

        for (int i = 1; i <= N; ++i) {
            c[i] = sc.nextInt();
            d[i] = sc.nextInt();
        }

        final int MAX_COIN = 50 * N;
        S = Math.min(S, MAX_COIN);
        Queue<Node> q = new PriorityQueue<>();
        q.add(new Node(1, S, 0));

        boolean[][] visit = new boolean[N + 1][MAX_COIN + 1];
        long[] ans = new long[N + 1];
        Arrays.fill(ans, Long.MAX_VALUE);
        while (!q.isEmpty()) {
            Node node = q.poll();
            if (visit[node.u][node.coin]) {
                continue;
            }
            visit[node.u][node.coin] = true;
            ans[node.u] = Math.min(ans[node.u], node.time);

            for (Edge e : adj.get(node.u)) {
                int coin = node.coin - e.A;
                if (coin >= 0) {
                    q.add(new Node(e.v, coin, node.time + e.B));
                }
            }

            int coin = Math.min(MAX_COIN, node.coin + c[node.u]);
            q.add(new Node(node.u, coin,node.time + d[node.u]));
        }

        for (int i = 2; i <= N; ++i) {
            System.out.println(ans[i]);
        }
    }

    public static void main(String[] args) {
        new Main().solve();
    }
}
