/**
* بسم الله الرحمن الرحيم *
﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿
*/
/// author : "ASGA"
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll inf=1e18;
ll solve(int n,int m,int w,vector<int>T,vector<int>X,vector<int>Y,vector<int>A,vector<int>B,vector<int>C,vector<int>L,vector<int>R){
vector<vector<array<int,4>>>a(n);
vector<vector<int>>b(n);
for(int i=0;i<m;i++){
a[X[i]].push_back({Y[i],A[i],B[i],C[i]});
a[Y[i]].push_back({X[i],A[i],B[i],C[i]});
b[X[i]].push_back(Y[i]);
b[Y[i]].push_back(X[i]);
}
for(auto&i:a)sort(i.begin(),i.end());
for(auto&i:b)sort(i.begin(),i.end());
if(w==0){
vector<int>l=L,r=R;
vector<vector<ll>>d(n);
for(int i=0;i<n;i++){
for(int j=0;j<a[i].size();j++){
d[i].push_back(inf);
}
}
/// c,j,i,t;
priority_queue<array<ll,4>,vector<array<ll,4>>,greater<array<ll,4>>>q;
for(int j=0;j<a[0].size();j++){
d[0][j]=a[0][j][3];
q.push({d[0][j],j,0,a[0][j][2]});
}
ll ans=inf;
while(!q.empty()){
int i=q.top()[1],p=q.top()[2],t=q.top()[3];
ll c=q.top()[0];
q.pop();
if(i==n-1)ans=min(ans,c);
if(d[p][lower_bound(b[p].begin(),b[p].end(),i)-b[p].begin()]<c)continue;
for(int j=0;j<a[i].size();j++){
if(a[i][j][1]>=t&&c+a[i][j][3]<d[i][j]){
d[i][j]=c+a[i][j][3];
q.push({d[i][j],j,i,a[i][j][2]});
}
}
}
return (ans<inf?ans:-1);
}
else{
;
}
return -1;
}
//signed main(){
// ios_base::sync_with_stdio(0);cin.tie(0);
//
//
//
// return 0;
//}
