#include "train.h"
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <vector>
const long long inf = 1e15;
long long solve(int N, int M, int W, std::vector<int> T, std::vector<int> X,
std::vector<int> Y, std::vector<int> A, std::vector<int> B,
std::vector<int> C, std::vector<int> L, std::vector<int> R) {
std::vector<std::vector<int>> node_times(N);
std::map<std::pair<int, int>,
std::vector<std::pair<std::pair<int, int>, int>>>
adj;
for (int i = 0; i < M; ++i) {
node_times[X[i]].push_back(A[i]);
node_times[Y[i]].push_back(B[i]);
adj[{X[i], A[i]}].push_back({{Y[i], B[i]}, C[i]});
}
node_times[0].push_back(0);
for (int i = 0; i < N; ++i) {
std::sort(node_times[i].begin(), node_times[i].end());
for (int j = 1; j < node_times[i].size(); ++j) {
adj[{i, node_times[i][j - 1]}].push_back({{i, node_times[i][j]}, 0});
}
}
std::set<std::pair<int, int>> vis;
std::map<std::pair<int, int>, long long> ans;
ans[{0, 0}] = 0;
std::priority_queue<std::pair<long long, std::pair<int, int>>> pq;
pq.push({0, {0, 0}});
while (!pq.empty()) {
auto [dist, u] = pq.top();
pq.pop();
if (vis.count(u)) {
continue;
}
vis.insert(u);
dist = -dist;
for (auto &i : adj[u]) {
if (!ans.count(i.first)) {
ans[i.first] = inf;
}
if (dist + i.second < ans[i.first]) {
ans[i.first] = dist + i.second;
pq.push({-ans[i.first], i.first});
}
}
}
if (node_times[N - 1].empty()) {
return -1;
}
long long ret = ans[{N - 1, node_times[N - 1].back()}];
if (ret == inf) {
ret = -1;
}
return ret;
}
