#include "escape_route.h"
#include <iostream>
#include <vector>
#include <array>
#include <queue>
#include <algorithm>
#define ll long long
using namespace std;
vector <array<ll, 4>> query;
ll adjid[90];
vector <array<ll, 3>> adj[90];
array <ll, 3> par_edge[90];
vector <array<ll, 3>> tree_edge[90][2];
vector <array<ll, 2>> queryb[90][90];
vector <array<ll, 2>> querya[90][90];
vector <array<ll, 2>> possibledist[90][90];
ll dist[90], rdist[90], X[90], fullday[90][90], reachable[90][90];
priority_queue <array<ll, 3>, vector<array<ll, 3>>, greater<array<ll, 3>>> pq;
priority_queue <array<ll, 2>> rpq;
ll n, q, s;
vector <ll> F;
std::vector<long long> calculate_necessary_time(
int N, int M, long long S, int Q, std::vector<int> A, std::vector<int> B,
std::vector<long long> L, std::vector<long long> C, std::vector<int> U,
std::vector<int> V, std::vector<long long> T) {
n = N, q = Q, s = S;
F.resize(q);
for (int i=0; i<M; ++i) {
adj[A[i]].push_back({B[i], C[i]-L[i], L[i]});
adj[B[i]].push_back({A[i], C[i]-L[i], L[i]});
}
for (int i=0; i<N; ++i) for (int j=0; j<N; ++j) reachable[i][j] = -1;
for (int i=0; i<N; ++i) {
for (int j=0; j<N; ++j) dist[j] = 1e18, X[j] = -1;
pq.push({0, i, 0});
dist[i] = 0, X[i] = s-1;
while (!pq.empty()) {
auto [w, u, t] = pq.top();
pq.pop();
if (dist[u] != w) continue;
for (auto [v, lim, len] : adj[u]) {
if (t <= lim && dist[v] > w+len) {
dist[v] = w+len;
pq.push({dist[v], v, t+len});
}
else if (t > lim && dist[v] > w+s-t+len) {
dist[v] = w+s-t+len;
pq.push({dist[v], v, len});
}
}
}
for (int j=0; j<N; ++j) fullday[i][j] = dist[j];
rpq.push({s-1, i});
while (!rpq.empty()) {
auto [w, u] = rpq.top();
rpq.pop();
if (X[u] != w) continue;
reachable[u][i] = X[u];
for (auto [v, lim, len] : adj[u]) {
if (X[v] < min(lim, X[u]-len)) {
X[v] = min(lim, X[u]-len);
rpq.push({X[v], v});
}
}
}
sort(adj[i].begin(), adj[i].end(), [](auto a, auto b) {
return a[1] < b[1];
});
}
for (int i=0; i<q; ++i) query.push_back({U[i], V[i], T[i], i});
sort(query.begin(), query.end(), [](auto a, auto b) {
return a[2] > b[2];
});
for (int i=0; i<q; ++i) {
if (reachable[query[i][0]][query[i][1]] >= query[i][2]) querya[query[i][0]][query[i][1]].push_back({query[i][2], query[i][3]});
else queryb[query[i][0]][query[i][1]].push_back({query[i][2], query[i][3]});
}
for (int i=0; i<n; ++i) {
for (int j=0; j<n; ++j) {
vector <array<ll, 2>> cur;
for (int k=0; k<n; ++k) {
if (reachable[i][k] >= 0) cur.push_back({reachable[i][k], fullday[k][j]});
}
ll f = 1e18;
sort(cur.begin(), cur.end());
for (auto [t, id] : queryb[i][j]) {
while (!cur.empty() && cur.back()[0] >= t) {
f = min(f, cur.back()[1]);
cur.pop_back();
}
F[id] = f+S-t;
}
}
}
for (int i=0; i<n; ++i) {
for (auto [ti, limi, leni] : adj[i]) {
for (int j=0; j<n; ++j) dist[j] = s, rdist[j] = -1e18;
dist[i] = rdist[i] = limi;
pq.push({limi, i, 0});
while (!pq.empty()) {
auto [w, u, t] = pq.top();
pq.pop();
if (dist[u] != w) continue;
for (auto [v, lim, len] : adj[u]) {
if (w <= lim && dist[v] > w+len) {
dist[v] = w+len;
pq.push({dist[v], v, 0});
}
}
}
rpq.push({limi, i});
while (!rpq.empty()) {
auto [w, u] = rpq.top();
rpq.pop();
if (rdist[u] != w) continue;
for (auto [v, lim, len] : adj[u]) {
if (rdist[v] < min(lim, w-len)) {
rdist[v] = min(lim, w-len);
rpq.push({rdist[v], v});
}
}
}
for (int x=0; x<n; ++x) {
for (int y=0; y<n; ++y) {
if (dist[y] >= s) continue;
possibledist[x][y].push_back({rdist[x], dist[y]-rdist[x]});
}
}
}
}
for (int i=0; i<n; ++i) {
for (int j=0; j<n; ++j) {
ll f = 1e18;
sort(possibledist[i][j].begin(), possibledist[i][j].end());
for (auto [t, id] : querya[i][j]) {
while (!possibledist[i][j].empty() && t <= possibledist[i][j].back()[0]) {
f = min(f, possibledist[i][j].back()[1]);
possibledist[i][j].pop_back();
}
if (f == 1e18) F[id] = possibledist[i][j].back()[1];
else F[id] = f;
}
}
}
return F;
}
