#include "train.h"
#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second
#define pp pop_back
#define ll long long
#define pb push_back
#define ls(v) (ll)v.size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define wr cout << "------------------------" << endl
const int MAXN = 1e5 + 5;
struct Train{
int planet;
int cost;
int start;
int end;
};
vector<Train> g[MAXN];
vector<int> in;
long long 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) {
const ll INF = 3e18;
map<pair<int, int>, ll> dp;
priority_queue<pair<ll, pair<int, int>>, vector<pair<ll, pair<int, int>>>, greater<pair<ll, pair<int, int>>>> pq;
for(int i = 0;i<M;++i){
g[X[i]].pb({Y[i], C[i], A[i], B[i]});
if(Y[i]==N-1)
in.push_back(B[i]);
if(X[i]==N-1)
in.push_back(A[i]);
}
dp[{0, 0}] = 0;
pq.push({0, {0, 0}});
while(!pq.empty()){
pair<ll, pair<int, int>> P=pq.top();
pq.pop();
int nd=P.ss.ff, time=P.ss.ss;
ll dis=P.ff;
ll val=dp[{nd, time}];
if(val!=dis)
continue;
for(auto &it: g[nd]){
if(time <= it.start){
ll cost = val + it.cost;
for(int i = 0;i<W;++i){
if(time < L[i] and R[i] < it.start){
cost += T[nd];
}
}
if(!dp.count({it.planet, it.end}) or cost < dp[{it.planet, it.end}]){
dp[{it.planet, it.end}]=cost;
pq.push({cost, {it.planet, it.end}});
}
}
}
}
ll ans=INF;
for(auto × : in)
if(dp.count({N-1, times})) ans=min(ans, dp[{N-1, times}]);
if(ans==INF)
ans=-1;
return ans;
}
