#include<bits/stdc++.h>
#define int long long
#define N 100005
using namespace std;
struct node{
	int v,w0,w1;
};
vector<node>e[N];
int n,m,t0,t1,t2,d[N];
bool check(int x){
	for(int i=1;i<=n;i++){
		d[i]=1e9+1;//就是这一行
	}
	d[1]=x;
	queue<int>q;
	q.push(1);
	while(!q.empty()){
		int t=q.front();
		q.pop();
		for(auto it:e[t]){
			int tim;
			if(d[t]+it.w0<=t1||d[t]>=t2)tim=it.w0+d[t];
			else tim=d[t]+min(t2-d[t]+it.w0,it.w1);
			if(d[it.v]>tim){
				d[it.v]=tim;
				q.push(it.v);
			}
		}
	}
	return d[n]<=t0;
}
void solve(int cs){
	cin>>n>>m>>t0>>t1>>t2;
	for(int i=1;i<=n;i++){
		e[i].clear();
	}
	int tmp;
	for(int i=1;i<=m;i++){
		int u,v,l0,l1;
		cin>>u>>v>>l0>>l1;
		if(i==1)tmp=v;
		e[u].push_back({v,l0,l1});
		e[v].push_back({u,l0,l1});
	}
	int l=0,r=t0,res=t0+1;
	while(l<=r){
		int mid=l+r>>1;
		if(check(mid)){
			l=mid+1;
			res=mid;
		}
		else r=mid-1;
	}
	if(res>t0)res=-1;
	cout<<res<<'\n';
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int T;
	cin>>T;
	for(int cs=1;cs<=T;cs++){
		solve(cs);
	}
	return 0;
}

我打注释的那一行，如果赋值成2e9或者2e18，就会在第21点上TLE，想问一下为什么?