#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;
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;
map<pair<int, int>, int> mp;
map<int, pair<int, int>> rmp;
vector<vector<pair<int, ll>>> g(M * 4 + 5);
vector<vector<int>> v(N, vector<int>());
mp[{0, 0}] = 1;
rmp[1] = {0, 0};
v[0].pb(0);
int id = 1;
for(int i = 0;i<M;++i){
int IDX = mp[{X[i], A[i]}];
int IDY = mp[{Y[i], B[i]}];
if(IDX == 0){
IDX = ++ id;
mp[{X[i], A[i]}] = IDX;
rmp[id] = {X[i], A[i]};
}
if(IDY == 0){
IDY = ++ id;
mp[{Y[i], B[i]}] = IDY;
rmp[id] = {Y[i], B[i]};
}
v[X[i]].pb(A[i]);
v[Y[i]].pb(B[i]);
assert(IDX < M * 4 + 1);
g[IDX].pb({C[i], IDY});
}
for(int i = 0;i<N;++i){
sort(all(v[i]));
v[i].erase(unique(all(v[i])), v[i].end());
for(int j = 1;j<ls(v[i]);++j){
int ID2 = mp[{i, v[i][j]}];
int ID1 = mp[{i, v[i][j - 1]}];
g[ID1].pb({0, ID2});
}
}
function<ll()> Dijkstra=[&](){
ll ans = INF;
vector<ll> dp(M * 4 + 5, INF);
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
pq.push({0, 1});
while(!pq.empty()){
auto [k, nd] = pq.top();
pq.pop();
if(dp[nd] <= k) continue;;
dp[nd] = k;
for(auto it:g[nd]){
ll cost = it.ff + k;
if(dp[it.ss] > cost){
pq.push({cost, it.ss});
}
}
}
for(auto it:rmp){
if(it.ss.ff == N - 1) ans = min(ans, dp[it.ff]);
}
if(ans >= INF) ans = -1;
return ans;
};
return Dijkstra();
}
