#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#include "train.h"
#define ll long long
#define INF (ll)1000000000000000000
struct route{
ll t1;
ll t0;
ll from;
ll dest;
ll cost;
ll totalCost;
const int operator<(route b){
return t1 < b.t1;
}
};
vector<vector<ll>> adj;
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){
adj.assign(N, {});
vector<route> paths;
for(ll i = 0; i<M; i++){
adj[X[i]].push_back(i);
adj[Y[i]].push_back(i);
paths.push_back({B[i], A[i], X[i], Y[i], C[i], INF});
}
for(ll i = 0; i<M; i++){
if(paths[i].from == 0) paths[i].totalCost = paths[i].cost;
}
sort(paths.begin(), paths.end());
for(ll i = 0; i<M; i++){
for(auto j : adj[paths[i].from]){
if(paths[j].dest == paths[i].from && paths[j].t1 <= paths[i].t0){
paths[i].totalCost = min(paths[i].totalCost, paths[j].totalCost + paths[i].cost);
}
}
}
ll ans = INF;
for(ll i = 0; i<M; i++){
if(paths[i].dest == N-1) ans = min(ans, paths[i].totalCost);
}
return ans;
}
