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.io.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        FastScanner sc = new FastScanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int S = sc.nextInt();
        int MAX = 2500;
        long INF = 1L << 60;
        ArrayList<ArrayList<Edge>> G = new ArrayList<>();
        long[] C = new long[N];
        long[] D = new long[N];
        for(int i = 0; i < N; i++){
            G.add(new ArrayList<>());
        }
        for(int i = 0; i < M; i++){
            int u = sc.nextInt()-1;
            int v = sc.nextInt()-1;
            int a = sc.nextInt();
            int b = sc.nextInt();
            G.get(u).add(new Edge(v,new Pair(a,b)));
            G.get(v).add(new Edge(u,new Pair(a,b)));
        }
        for(int i = 0; i < N; i++){
            C[i] = sc.nextInt();
            D[i] = sc.nextInt();
        }
        if(S >= MAX) S = MAX;
        long[][] dp = new long[N][MAX+1];
        for(int i = 0; i < N; i++){
            Arrays.fill(dp[i],INF);
        }
        PriorityQueue<QueueItem> q = new PriorityQueue<>();
        dp[0][S] = 0;
        q.add(new QueueItem(0,0,S));
        while (q.size() > 0) {
            QueueItem p = q.poll();
            long time = p.t;
            int v = p.v;
            long s = p.s;
            if (time > dp[v][(int)s]) continue;
    
            // 補充
            long ns2 = Math.min(MAX,s + C[v]);
            long ntime2 = time + D[v];
            if(dp[v][(int)ns2] > ntime2){
                dp[v][(int)ns2] = ntime2;
                q.add(new QueueItem(ntime2,v,ns2));
            }
            // 辺を通る
            for (Edge e : G.get(v)){
                if(s < e.p.m){
                    continue;
                }
                int nv = e.v;
                long ns = s-e.p.m;
                long ntime = time + e.p.t;
                if(dp[nv][(int)ns] > ntime){
                    dp[nv][(int)ns] = ntime;
                    q.add(new QueueItem(ntime,nv,ns));
                }
            }
        }
        for (int v = 1; v < N; v++){
            long ans = INF;
            for(int s = 0; s <= MAX; s++){
                ans = Math.min(ans,dp[v][s]);
            }
            pw.println(ans);
        }
        pw.flush();
    }
}

class Pair{
    long m,t;
    public Pair(long m, long t){
        this.m = m;
        this.t = t;
    }
}

class Edge{
    int v;
    Pair p;
    public Edge(int v, Pair p){
        this.v = v;
        this.p = p;
    }
}

class QueueItem implements Comparable<QueueItem>{
    long t,s;
    int v;
    public QueueItem(long t, int v, long s){
        this.t = t;
        this.v = v;
        this.s = s;
    }
    
    public int compareTo(QueueItem q){
        if(this.t < q.t){
            return -1;
        }else if(this.t > q.t){
            return 1;
        }else{
            return 0;
        }
    }
}

class FastScanner {
    private BufferedReader reader = null;
    private StringTokenizer tokenizer = null;
    public FastScanner(InputStream in) {
        reader = new BufferedReader(new InputStreamReader(in));
        tokenizer = null;
    }

    public String next() {
        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    public String nextLine() {
        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                return reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken("\n");
    }

    public long nextLong() {
        return Long.parseLong(next());
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public double nextDouble() {
         return Double.parseDouble(next());
    }
    
    public String[] nextArray(int n) {
        String[] a = new String[n];
        for (int i = 0; i < n; i++)
            a[i] = next();
        return a;
    }

    public int[] nextIntArray(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = nextInt();
        return a;
    }

    public long[] nextLongArray(int n) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++)
            a[i] = nextLong();
        return a;
    } 
}
