#include <bits/stdc++.h>
#include "escape_route.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define fr first
#define sc second
const ll inf = 1e18;
vector<ll> calculate_necessary_time(int N, int M, ll S, int Q, vector<int> A, vector<int> B,
vector<ll> L, vector<ll> C, vector<int> U, vector<int> V, vector<ll> T)
{
vector<vector<ll>> c(N, vector<ll>(N, S));
vector<vector<ll>> l(N, vector<ll>(N, S));
for (int i = 0; i < M; i ++)
{
c[A[i]][B[i]] = c[B[i]][A[i]] = C[i];
l[A[i]][B[i]] = l[B[i]][A[i]] = L[i];
}
for (int i = 0; i < N; i ++)
c[i][i] = l[i][i] = 0;
auto dijkstra = [&](int p, int s)
{
vector<ll> d(N, inf);
vector<bool> used(N, false);
d[s] = c[p][s];
for (int turip = 0; turip < N; turip ++)
{
int u = -1;
for (int i = 0; i < N; i ++)
if (!used[i] && (u == -1 || d[i] < d[u]))
u = i;
used[u] = true;
for (int v = 0; v < N; v ++)
{
if (used[v] || c[u][v] >= S)
continue;
ll dd = d[u] + l[u][v];
if (d[u] % S + l[u][v] > c[u][v])
dd += S - d[u] % S;
d[v] = min(d[v], dd);
}
}
return d;
};
vector<vector<vector<ll>>> d(N, vector<vector<ll>> (N, vector<ll>(N, inf)));
for (int i = 0; i < N; i ++)
for (int j = 0; j < N; j ++)
if (c[i][j] < S)
d[i][j] = dijkstra(i, j);
vector<ll> res(Q, inf);
for (int i = 0; i < Q; i ++)
res[i]= d[U[i]][U[i]][V[i]] + (S - T[i]) % S;
for (int st = 0; st < N; st ++)
{
vector<pair<ll,int>> qq;
for (int i = 0; i < Q; i ++)
if(U[i] == st)
qq.push_back({T[i], i});
sort(qq.begin(), qq.end());
vector<vector<pair<ll, int>>> ord(N);
for (int i = 0; i < N; i ++)
{
for (int j = 0; j < N; j ++)
if (i != j && c[i][j] < S)
ord[i].push_back({c[i][j] - l[i][j], j});
sort(ord[i].rbegin(), ord[i].rend());
}
vector<int> pos(N, 0);
vector<ll> dd(N, inf);
dd[st] = 0;
while (!qq.empty())
{
pair<ll, int> Max = {-1, -1};
for (int i = 0; i < N; i ++)
if (pos[i] < (int)ord[i].size())
Max = max(Max, {ord[i][pos[i]].fr - dd[i], i});
while (!qq.empty() && qq.back().fr > Max.fr)
{
int id = qq.back().sc;
qq.pop_back();
res[id] = min(res[id], dd[V[id]]);
for (int i = 0; i < N; i ++)
{
if (dd[i] == inf)
continue;
res[id] = min(res[id], S - T[id] + d[i][i][V[id]]);
}
}
if(Max.fr == -1)
break;
int u = Max.sc;
int v = ord[u][pos[Max.sc] ++].sc;
for (int i = 0; i < N; i ++)
if(d[u][v][i] < S)
dd[i] = min(dd[i], d[u][v][i] - Max.fr);
}
}
return res;
}
