#include "train.h"
#include <bits/stdc++.h>
using namespace std;
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) {
vector<vector<array<int, 4> > > f(n+1);
for(int i = 0; i < m; i++) {
f[X[i]].push_back({Y[i], A[i], B[i], C[i]});
f[Y[i]].push_back({X[i], A[i], B[i], C[i]});
}
vector<pair<int, int> > dis(n+1, {-1, -1});
dis[1] = {0, 0};
priority_queue<pair<pair<int, int>, int> > pqq;
pqq.push({dis[1], 1});
while(pqq.size()) {
auto [w, id] = pqq.top(); pqq.pop();
w.first = -w.first;
w.second = -w.second;
if(dis[id] != w) continue;
for(auto &[d, st, en, cost] : f[id]) {
if(dis[d] == make_pair(-1, -1) || dis[d] > make_pair(w.first + cost, en)) {
dis[d] = make_pair(w.first + cost, en);
pqq.push({make_pair(-dis[d].first, -dis[d].second), d});
}
}
}
return dis[n].first;
}
