#include "escape_route.h"
#include <bits/stdc++.h>
using namespace std;
vector<long long> calculate_necessary_time(int n, int m, long long S, int q, vector<int> A, vector<int> B, vector<long long> L, vector<long long> C, vector<int> U, vector<int> V, vector<long long> T) {
const long long INF = 4e18;
vector<vector<pair<int, int>>> adj(n);
for (int i = 0; i < m; i++) {
int u = A[i];
int v = B[i];
adj[u].push_back({v, i});
adj[v].push_back({u, i});
}
auto [f, g] = [&]() -> pair<vector<vector<vector<long long>>>, vector<vector<long long>>> {
vector<vector<vector<long long>>> f(n);
vector<vector<long long>> g(n);
for (int s = 0; s < n; s++) {
long long t = 0;
while (true) {
vector<long long> dist(n, INF);
vector<int> par(n, -1);
vector<bool> popped(n, false);
dist[s] = 0;
while (true) {
int u = -1;
long long mn = INF;
for (int v = 0; v < n; v++) {
if (popped[v]) continue;
if (dist[v] < mn) {
u = v;
mn = dist[v];
}
}
if (u == -1) break;
popped[u] = true;
for (auto [v, i] : adj[u]) {
if (t + dist[u] + L[i] > C[i]) continue;
if (dist[u] + L[i] < dist[v]) {
dist[v] = dist[u] + L[i];
par[v] = i;
}
}
}
g[s].push_back(t);
f[s].push_back(dist);
long long new_t = INF;
for (int u = 0; u < n; u++) {
if (par[u] == -1) continue;
new_t = min(new_t, C[par[u]] - dist[u] + 1);
}
if (new_t >= S || new_t == t) break;
t = new_t;
}
}
return make_pair(f, g);
}();
vector<vector<long long>> dist = [&]() -> vector<vector<long long>> {
vector<vector<long long>> dist(n, vector<long long>(n, INF));
for (int u = 0; u < n; u++) {
for (int v = 0; v < n; v++) {
if (u == v) dist[u][v] = 0;
else if (f[u][0][v] != INF) dist[u][v] = S;
}
}
for (int k = 0; k < n; k++) {
for (int u = 0; u < n; u++) {
for (int v = 0; v < n; v++) {
dist[u][v] = min(dist[u][v], dist[u][k] + dist[k][v]);
}
}
}
vector<vector<long long>> true_dist(n, vector<long long>(n, INF));
for (int u = 0; u < n; u++) {
for (int v = 0; v < n; v++) {
for (int w = 0; w < n; w++) {
true_dist[u][v] = min(true_dist[u][v], dist[u][w] + f[w][0][v]);
}
}
}
return true_dist;
}();
vector<vector<vector<long long>>> F = f; {
for (int u = 0; u < n; u++) {
for (int i = 0; i < f[u].size(); i++) {
for (int w = 0; w < n; w++) {
if (f[u][i][w] != INF) {
for (int v = 0; v < n; v++) {
F[u][i][v] = min(F[u][i][v], dist[w][v]);
}
}
}
}
}
}
return [&]() -> vector<long long> {
auto query = [&](int u, int v, long long t) -> long long {
int i = upper_bound(g[u].begin(), g[u].end(), t) - g[u].begin() - 1;
if (f[u][i][v] != INF) return f[u][i][v];
long long ans = S - t + F[u][i][v];
return ans;
};
vector<long long> ans(q);
for (int i = 0; i < q; i++) {
ans[i] = query(U[i], V[i], T[i]);
}
return ans;
}();
}
