import java.util.*;

public class TaxiAStar {
	class Node implements Comparable<Node> {
		int harga, waktu, pos;

		public Node(int harga, int waktu, int pos){
			this.harga = harga;
			this.waktu = waktu;
			this.pos = pos;
		}

		public int compareTo(Node that){
			return this.harga - that.harga;
		}
	}

	int[][] harga;
	int[][] waktu;
	int[] bestTime;

	public void solve(){
		Scanner scan = new Scanner(System.in);

		while (scan.hasNextInt()){
			int N = scan.nextInt();
			int M = scan.nextInt();

			harga = new int[N][N];
			waktu = new int[N][N];
			bestTime = new int[N];

			for (int i=0; i<N; i++){
				for (int j=0; j<N; j++)
					waktu[i][j] = -1;
				bestTime[i] = 1000000000;
			}

			for (int i=0; i<M; i++){
				int u = scan.nextInt();
				int v = scan.nextInt();
				int t = scan.nextInt();
				int c = scan.nextInt();
				waktu[u][v] = waktu[v][u] = t;
				harga[u][v] = harga[v][u] = c;
			}

			int A = scan.nextInt();
			int B = scan.nextInt();
			int R = scan.nextInt();

			PriorityQueue<Node> pq = new PriorityQueue<Node>();
			pq.offer(new Node(0,0,A));
			while (pq.size()>0){
				Node node = pq.poll();

				if (bestTime[node.pos] <= node.waktu) continue;
				bestTime[node.pos] = node.waktu;
				if (node.pos == B) continue;

				for (int i=0; i<N; i++){
					if (waktu[node.pos][i]==-1) continue;
					if (node.harga + harga[node.pos][i] > R) continue;
					pq.offer(new Node(
						node.harga + harga[node.pos][i],
						node.waktu + waktu[node.pos][i],
						i
					));
				}
			}
			
			System.out.printf("%d\n",bestTime[B]);
		}

		scan.close();
	}

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