#include "train.h"
#include "bits/stdc++.h"
#define ll long long
#define ff first
#define ss second
using namespace std;
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 <int>> v(n);
v[0].push_back(0);
for (int i = 0;i < m;i++){
v[x[i]].push_back(a[i]);
v[y[i]].push_back(b[i]);
}
for (int i = 0;i < n;i++){
sort(v[i].begin(),v[i].end());
v[i].erase(unique(v[i].begin(),v[i].end()),v[i].end());
}
vector <int> pr(n+1);
for (int i = 1;i <= n;i++){
pr[i] = pr[i-1] + v[i-1].size();
}
auto id = [&](int in,int h){
int pos = lower_bound(v[in].begin(),v[in].end(),h) - v[in].begin();
return pr[in] + pos;
};
int k = pr[n];
vector <vector <pair<int,ll>>> g(k);
for (int i = 0;i < m;i++){
int u = id(x[i],a[i]);
int v = id(y[i],b[i]);
g[u].push_back({v,c[i]});
}
for (int j = 0;j < n;j++){
for (int i = 0;i < v[j].size()-1;i++){
int u = pr[j] + i;
int v = pr[j] + i+1;
g[u].push_back({v,0});
}
}
vector <ll> dt(k,inf);
priority_queue <pair<ll,int>> q;
int st = id(0,0);
dt[st] = 0;
q.push({0,st});
while (!q.empty()){
ll d = -q.top().ff;
int nd = q.top().ss;
q.pop();
if (d > dt[nd])
continue;
for (auto& j : g[nd]){
int to = j.ff;
ll wt = j.ss;
if (dt[nd] + wt < dt[to]){
dt[to] = dt[nd] + wt;
q.push({-dt[to],to});
}
}
}
ll p = inf;
for (int i = 0;i < v[n-1].size();i++){
p = min(p,dt[pr[n-1]+i]);
}
if (p == inf)
p = -1;
return p;
}
