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.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;

public class Main implements Runnable
{
//    static int dx[]={-1,0,1,0};
//    static int dy[]={0,-1,0,1};
    static long mod=1000000007;
    
    public static void main(String[] args) {        
        new Thread(null, new Main(), "", 200 * 1024 * 1024).start();        
    }

    public void run() {
        Reader sc = new Reader(System.in);
        PrintWriter out=new PrintWriter(System.out);

        int n=sc.nextInt();
        int m=sc.nextInt();
        int s=sc.nextInt();
        int ed[][]=new int[n][100];
        int dg[]=new int[n];
        int sf=10,bt=(1<<sf)-1;
        int e[][]=new int[m][2];
        int ex[][]=new int[n][2];
        for (int i = 0; i < m; i++) {
			int f=sc.nextInt()-1,t=sc.nextInt()-1;
			ed[f][dg[f]++]=(t<<sf)+i;
			ed[t][dg[t]++]=(f<<sf)+i;
			e[i][0]=sc.nextInt();
			e[i][1]=sc.nextInt();
		}
        for (int i = 0; i < ex.length; i++) {
			ex[i][0]=sc.nextInt();
			ex[i][1]=sc.nextInt();
		}
        
        long d[][]=new long[50][3001];
        for (int i = 0; i < d.length; i++) {
			fill(d[i], 1L<<50);
		}
        
        PriorityQueue<P> q=new PriorityQueue<>();
        s=min(s,2500);
        d[0][s]=0;
        q.add(new P(0,s,0));

        while(!q.isEmpty()) {
        	P p=q.poll();
//        	db(p.x,p.c,p.s);
        	d[p.x][3000]=min(p.s,d[p.x][3000]);
        	if(p.s>d[p.x][p.c])continue;
			if(p.c+ex[p.x][0]<=2500 && p.s+ex[p.x][1] < d[p.x][p.c+ex[p.x][0]]) {
				d[p.x][p.c + ex[p.x][0]] = p.s + ex[p.x][1];
				q.add(new P(p.x, p.c + ex[p.x][0], p.s + ex[p.x][1]));
			}
			for (int i = 0,to,id; i < dg[p.x]; i++) {
				id = ed[p.x][i];
				to=id>>sf;
				id=id&bt;
				if(p.c < e[id][0])continue;
				if(p.s + e[id][1] < d[to][p.c-e[id][0]]) {
					d[to][p.c-e[id][0]] = p.s + e[id][1];
					q.add(new P(to, p.c - e[id][0], p.s + e[id][1]));
				}
			}
        }
        for (int i = 1; i < n; i++) {
			out.println(d[i][3000]);
		}
    
        out.println();
     	out.flush();
    }

    static void ret(String ans) {
    	System.out.println(ans);
    	System.exit(0);
    }

    static void ret(long ans) {
    	System.out.println(ans);
    	System.exit(0);
    }
    
    static boolean validpos(int x,int y,int r, int c){
        return x<r && 0<=x && y<c && 0<=y;
    }

    static void db(Object... os){
        System.err.println(Arrays.deepToString(os));
    }
}

//class P {
//	int x,c;long s;
//	P(int  x, int c, long s) {
//	  this.x=x;
//	  this.c=c;
//	  this.s=s;
//	}
//}


class P implements Comparable<P>{
	int x,c;long s;
	P(int  x, int c, long s) {
	  this.x=x;
	  this.c=c;
	  this.s=s;
	}

    public int compareTo(P p){
        return Long.signum(s-p.s);
    }
}

class Reader
{ 
    private BufferedReader x;
    private StringTokenizer st;
    
    public Reader(InputStream in)
    {
        x = new BufferedReader(new InputStreamReader(in));
        st = null;
    }
    public String nextString()
    {
        while( st==null || !st.hasMoreTokens() )
			try {
				st = new StringTokenizer(x.readLine());
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
        return st.nextToken();
    }
    public int nextInt()
    {
        return Integer.parseInt(nextString());
    }
    public int[] nextIntArray(int size) {
        int r[] = new int[size];
        for (int i = 0; i < size; i++) {
            r[i] = this.nextInt(); 
        }
        return r;
    }
    public long[] nextLongArray(int size) {
        long r[] = new long[size];
        for (int i = 0; i < size; i++) {
            r[i] = this.nextLong(); 
        }
        return r;
    }
    public char[] getCharSet() {
        return this.nextString().toCharArray();
    }    
    public long nextLong()
    {
        return Long.parseLong(nextString());
    }
    public double nextDouble() throws IOException
    {
        return Double.parseDouble(nextString());
    }
}
