#include "train.h"
#include "bits/stdc++.h"
#define ff first
#define ss second
#define pp pop_back
#define ll long long
#define pb push_back
#define ls(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define wr cout << "------------------------" << endl
using namespace std;
struct Trains{
int x;
int y;
int a;
int b;
int c;
};
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 = 1e18;
vector<vector<pair<int, ll>>> pref(N, vector<pair<int, ll>>());
vector<Trains> train(M);
for(int i = 0;i<M;++i) train[i] = {X[i], Y[i], A[i], B[i], C[i]};
sort(all(train), [](const Trains& a, const Trains& b){
return a.b < b.b;
});
pref[0].pb({0, 0});
for(int i = 0;i<M;++i){
int l = 0, r = ls(pref[train[i].x]) - 1;
ll res = INF;
while(l <= r){
int mid = l + r >> 1;
if(pref[train[i].x][mid].ff <= train[i].a) res = pref[train[i].x][mid].ss, l = mid + 1;
else r = mid - 1;
}
res += train[i].c;
if(pref[train[i].y].empty() or pref[train[i].y].back().ss > res) pref[train[i].y].pb({train[i].b, res});
}
ll ans = INF;
for(auto it:pref[N - 1]) ans = min(ans, it.ss);
if(ans >= INF) ans = -1;
return ans;
}
