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.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;
import java.util.concurrent.PriorityBlockingQueue;

public class Main {

    public static void main(String[] args) {
        FastScanner sc = new FastScanner();
        int n = sc.nextInt();
        int m = sc.nextInt();
        int s = sc.nextInt();

        City[] cities = new City[n];
        for (int i = 0; i < n; i++) {
            cities[i] = new City(i);
        }
        for (int i = 0; i < m; i++) {
            int mu = sc.nextInt() - 1;
            int mv = sc.nextInt() - 1;
            int ma = sc.nextInt();
            int mb = sc.nextInt();
            cities[mu].addNext(mv, ma, mb);
            cities[mv].addNext(mu, ma, mb);
        }
        for (int i = 0; i < n; i++) {
            int mc = sc.nextInt();
            int md = sc.nextInt();
            cities[i].setRate(mc, md);
        }

        s = Math.min(s, 2500);
        for (int i = 0; i <= s; i++) {
            cities[0].len[i] = 0;
        }

        PriorityQueue<Long[]> que = new PriorityQueue<Long[]>((a, b) -> Long.compare(a[2], b[2])); // id, coin, time;

        que.add(new Long[]{0l, (long)s, 0l});
        int count = 0;

        HashMap<Long, Integer> map = new HashMap<>();

        while(!que.isEmpty()){
            Long[] next = que.poll();

            count++;

            long mkey = next[0] * 1000000000l + next[1];
            if(map.containsKey(mkey)){
                continue;
            }else{
                map.put(mkey, 1);
            }

            int mid = (int)((long)(next[0]));
            long mcoin = next[1];
            long mtime = next[2];

            // System.out.println(mid + " " + mcoin + " " + mtime);
            // if(count > 10000) break;

            for (int i = (int)mcoin; i >= 0; i--) {
                if(cities[mid].len[i] == -1 || cities[mid].len[i] > mtime){
                    cities[mid].len[i] = mtime;
                }else{
                    break;
                }
            }
            
            for(Integer[] mnext : cities[mid].next){
                int nid = mnext[0];
                long nfee = mnext[1];
                long ntime = mnext[2];
                if(nfee <= mcoin){
                    if(cities[nid].len[(int)(mcoin - nfee)] > mtime + ntime || cities[nid].len[(int)(mcoin - nfee)] == -1){
                        que.add(new Long[]{(long)nid, mcoin - nfee, mtime + ntime});
                    }
                }
            }
            
            if(mcoin < 2500){
                int ncoin = (int)Math.min(2500, mcoin + cities[mid].rate);
                if(cities[mid].len[ncoin] == -1 || cities[mid].len[ncoin] > mtime + cities[mid].cTime){
                    que.add(new Long[]{(long)mid, (long)ncoin, mtime + cities[mid].cTime});
                }
            }
        }

        for (int i = 1; i < cities.length; i++) {
            System.out.println(cities[i].len[0]);
        }

        // System.out.println(count);
    }

    private static class FastScanner {
        private final InputStream in = System.in;
        private final byte[] buffer = new byte[1024];
        private int ptr = 0;
        private int buflen = 0;

        private boolean hasNextByte() {
            if (ptr < buflen) {
                return true;
            } else {
                ptr = 0;
                try {
                    buflen = in.read(buffer);
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (buflen <= 0) {
                    return false;
                }
            }
            return true;
        }

        private int readByte() {
            if (hasNextByte())
                return buffer[ptr++];
            else
                return -1;
        }

        private static boolean isPrintableChar(int c) {
            return 33 <= c && c <= 126;
        }

        public boolean hasNext() {
            while (hasNextByte() && !isPrintableChar(buffer[ptr]))
                ptr++;
            return hasNextByte();
        }

        public String next() {
            if (!hasNext())
                throw new NoSuchElementException();
            StringBuilder sb = new StringBuilder();
            int b = readByte();
            while (isPrintableChar(b)) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }

        public long nextLong() {
            if (!hasNext())
                throw new NoSuchElementException();
            long n = 0;
            boolean minus = false;
            int b = readByte();
            if (b == '-') {
                minus = true;
                b = readByte();
            }
            if (b < '0' || '9' < b) {
                throw new NumberFormatException();
            }
            while (true) {
                if ('0' <= b && b <= '9') {
                    n *= 10;
                    n += b - '0';
                } else if (b == -1 || !isPrintableChar(b)) {
                    return minus ? -n : n;
                } else {
                    throw new NumberFormatException();
                }
                b = readByte();
            }
        }

        public int nextInt() {
            long nl = nextLong();
            if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
                throw new NumberFormatException();
            return (int) nl;
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }

}

class City{
    int id;
    int rate;
    int cTime;
    ArrayList<Integer[]> next;  // id, fee
    long[] len;

    public City(int id){
        this.id = id;
        next = new ArrayList<Integer[]>();
        len = new long[2501];
        Arrays.fill(len, -1);
    }

    public void addNext(int id, int fee, int time){
        next.add(new Integer[]{id, fee, time});
    }

    public void setRate(int rate, int time){
        this.rate = rate;
        cTime = time;
    }
}

