#include <stdio.h>
#include <stdlib.h>

#define MAXN 105
#define INF 1000000

typedef struct {
	int harga, waktu, pos;
} Node;

int nodecmp(const void *a, const void *b){
	Node *na = (Node*) a;
	Node *nb = (Node*) b;
	return na->harga - nb->harga;
}

Node pq[100000];
int harga[MAXN][MAXN];
int waktu[MAXN][MAXN];
int bestTime[MAXN];

int main(){
	int n,m,u,v,t,c,duit,i,pqSize;

	while (scanf("%d %d",&n,&m)!=EOF){
		for (u=0; u<n; u++){
			for (v=0; v<n; v++) waktu[u][v] = -1;
			bestTime[u] = INF;
		}

		for (i=0; i<m; i++){
			scanf("%d %d %d %d",&u,&v,&t,&c);
			waktu[u][v] = waktu[v][u] = t;
			harga[u][v] = harga[v][u] = c;
		}
		scanf("%d %d %d",&u,&v,&duit);

		pq[0] = (Node){0,0,u};
		pqSize = 1;
		while (pqSize > 0){
			qsort(pq,pqSize,sizeof(Node),nodecmp); // sort berdasarkan harga termurah
			Node node = pq[0];
			pq[0] = pq[--pqSize]; // timpa elemen pertama dengan terakhir

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

			for (i=0; i<n; i++) {
				if (waktu[node.pos][i]==-1) continue;
				if (node.harga + harga[node.pos][i] > duit) continue;
				pq[pqSize++] = (Node){
					node.harga + harga[node.pos][i],
					node.waktu + waktu[node.pos][i],
					i
				};
			}
		}
		
		printf("%d\n",bestTime[v]);
	}
}
