#include "train.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <typename T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
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)
{
// the second subtask
vector adj(N, vector<tuple<int, int, int, int>>()); // x[i] = {y[i], b[i], c[i]}
for(int i = 0; i < M; i++)
adj[X[i]].push_back({Y[i], B[i], C[i], A[i]});
pqg<tuple<ll, int, int>> pq; // cost, lst, u
map<pair<int, int>, ll> dp;
pq.push({0, 0, 0});
while(not pq.empty())
{
auto [cost, lst, u] = pq.top();
pq.pop();
if(dp.find({u, lst}) != dp.end() and dp[{u, lst}] <= cost)
continue;
dp[{u, lst}] = cost;
if(u == N - 1)
break;
for(auto [y, b, c, a]: adj[u])
{
if(a >= lst)
{
pq.push({cost + c, b, y});
}
}
}
ll res = 1e18;
for(auto [f, s]: dp)
{
if(f.first == N - 1)
{
if(res > s)
res = s;
}
}
if(res == 1e18)
res = -1;
return res;
}
