#include "train.h"
#include <bits/stdc++.h>
#define int long long
#define emb emplace_back
#define pii pair <int, int>
#define tiii tuple <int, int, int>
#define tiiii tuple <int, int, int, int>
#define tdii tuple <double, int, int>
#define all(a) a.begin(), a.end()
using namespace std;
const int N = 1e5 + 5;
const int inf = 1e18;
long long solve(int32_t n, int32_t m, int32_t w, vector<int32_t> t, vector<int32_t> x, vector<int32_t> y,
vector<int32_t> a, vector<int32_t> b, vector<int32_t> c, vector<int32_t> l, vector<int32_t> r) {
vector <tiiii> adj[n + 1];
for (int i = 0; i < m; i++) {
adj[x[i]].emb(a[i], b[i], c[i], y[i]);
}
for (int i = 0; i < n; i++) sort(all(adj[i]));
priority_queue <tiii, vector <tiii>, greater <tiii>> q; q.emplace(0, 0, 0);
map <int, int> dis[n + 1];
for (int i = 0; i < n; i++) {
int sz = adj[i].size();
while (sz--) dis[i][sz] = inf;
}
dis[0][0] = 0;
int ans = inf;
while (!q.empty()) {
auto [w, u, idx] = q.top(); q.pop();
if (w > dis[u][idx]) continue;
if (idx + 1 < adj[u].size()) {
if (w < dis[u][idx + 1]) {
dis[u][idx + 1] = w;
q.emplace(dis[u][idx + 1], u, idx + 1);
}
}
if (adj[u].size() > idx) {
auto [aa, bb, ww, v] = adj[u][idx];
int nw = w + ww;
if (v == n - 1) ans = min(ans, nw);
int nxt = lower_bound(all(adj[v]), make_tuple(bb, 0, 0, 0)) - adj[v].begin();
if (nxt < adj[v].size()) {
if (nw < dis[v][nxt]) {
dis[v][nxt] = nw;
q.emplace(dis[v][nxt], v, nxt);
}
}
}
}
return (ans == inf ? -1ll : ans);
}
