#include "train.h"
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
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)
{
ll dp[n], ndp[n];
dp[0] = 0;
for (ll i = 1; i < n; i++)
dp[i] = 1e18;
array<ll, 5> edges[m];
for (ll i = 0; i < m; i++)
edges[i] = {X[i], Y[i], A[i], B[i], C[i]};
sort(edges, edges + m, [&](array<ll, 5> &a, array<ll, 5> &b)
{
return a[3] < b[3];
});
vector<pair<ll, ll>> cur[n];
for (ll i = 1; i < n; i++)
cur[i] = {make_pair((ll)-1, (ll)1e18)};
cur[0] = {make_pair((ll)-1, 0)};
L.insert(L.begin(), 0);
R.insert(R.begin(), 1e9);
T.insert(T.begin(), 0);
w++;
for (ll j = 0; j < w; j++)
{
for (ll i = 0; i < n; i++)
ndp[i] = 1e18, cur[i] = {make_pair((ll)-1, dp[i])};
for (auto [x, y, a, b, c] : edges)
{
for (ll i = 0; i < cur[x].size(); i++)
if (cur[x][i].first < a)
{
if (R[j] > b)
ndp[y] = min({ndp[y], cur[x][i].second + T[j] + c});
if (max(a, (ll)L[j]) <= min(b, (ll)R[j]))
ndp[y] = min(ndp[y], cur[x][i].second + c);
ndp[y] = min(ndp[y], ndp[x] + c);
}
ndp[y] = min(ndp[y], dp[y] + T[j] + c);
cur[y].push_back(make_pair(b, dp[y]));
}
for (ll i = 0; i < n; i++)
dp[i] = ndp[i];
}
return dp[n - 1] == 1e18 ? -1 : dp[n - 1];
}
