#include "train.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e18;
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){
map<pair<ll,ll>,vector<pair<pair<ll,ll>,ll>>> g;
vector<ll> z[n];
z[0].push_back(0);
for(ll i=0; i<m; i++){
g[{x[i],a[i]}].push_back({{y[i],b[i]},c[i]});
z[x[i]].push_back(a[i]);
z[y[i]].push_back(b[i]);
}
for(ll i=0; i<n; i++){
sort(z[i].begin(),z[i].end());
for(ll j=1; j<z[i].size(); j++){
g[{i,z[i][j-1]}].push_back({{i,z[i][j]},0});
}
}
map<pair<ll,ll>,ll> dist;
dist[{0,0}]=0;
map<pair<ll,ll>,bool> vis;
priority_queue<pair<ll,pair<ll,ll>>> q; q.push({0,{0,0}});
while(!q.empty()){
pair<ll,ll> curr=q.top().second;
q.pop();
if(vis[curr]) continue;
vis[curr]=1;
for(auto nxt:g[curr]){
if(dist.find(nxt.first)==dist.end() || dist[nxt.first]>dist[curr]+nxt.second){
dist[nxt.first]=dist[curr]+nxt.second;
q.push({-dist[nxt.first],nxt.first});
}
}
}
if(z[n-1].empty() || dist[{n-1,z[n-1].back()}]==INF) return -1;
else return dist[{n-1,z[n-1].back()}];
}
