#include <stdio.h>
#include <string.h>

int n,A,B,inf=1000000000;
int waktu[100][100];
int harga[100][100];
int memo[100][101];

int fastest(int P, int R){
	int i, ret = inf;
	if (P==B) return 0;
	if (memo[P][R]!=-1) return memo[P][R];

	for (i=0; i<n; i++){
		if (waktu[P][i]!=-1 && R>=harga[P][i]){
			int t = waktu[P][i] + fastest(i,R-harga[P][i]);
			if (t < ret) ret = t;
		}
	}
	return memo[P][R] = ret;
}

int main(){
	int m,u,v,t,c,i,R;
	
	while (scanf("%d %d",&n,&m)!=EOF){
		memset(waktu,-1,sizeof(waktu));
		memset(harga,-1,sizeof(harga));
		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",&A,&B,&R);
		memset(memo,-1,sizeof(memo));
		printf("%d\n",fastest(A,R));
	}
}
