#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
const ll inf = 1e18;
struct aboba {
ll time;
ll extend;
ll node;
};
bool operator < (aboba a, aboba b) {
if (a.time == b.time) {
return a.extend < b.extend;
}
return a.time > b.time;
}
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<array<ll, 3>>> g(N);
for (int i = 0; i < M; i += 1) {
g[A[i]].push_back({B[i], L[i], C[i]});
g[B[i]].push_back({A[i], L[i], C[i]});
}
vector<vector<vector<pair<ll, ll>>>> paths(N, vector<vector<pair<ll, ll>>>(N));
vector<vector<ll>> zero_delay(N, vector<ll>(N, inf));
for (int u = 0; u < N; u += 1) {
priority_queue<aboba> pq;
pq.push({0, -inf, u});
paths[u][u].push_back({0, inf});
vector<int> vis(N);
while (!pq.empty()) {
aboba x = pq.top();
pq.pop();
ll t = -x.time;
ll e = -x.extend;
int node = x.node;
if (vis[node] > 200) {
break;
}
vis[node] += 1;
for (auto [v, l, c] : g[node]) {
ll could = c - (t + l);
if (could < 0) {
continue;
}
bool bad = 0;
for (auto [time, extend] : paths[u][v]) {
if (t + l >= time && min(e, could) <= extend) {
bad = 1;
break;
}
}
if (!bad) {
zero_delay[u][v] = min(zero_delay[u][v], t + l);
paths[u][v].push_back({t + l, min(e, could)});
pq.push({-(t + l), -min(e, could), v});
}
}
}
}
for (int u = 0; u < N; u += 1) {
zero_delay[u][u] = 0;
}
vector<vector<ll>> dist(N, vector<ll>(N, inf));
for (int u = 0; u < N; u += 1) {
for (int v = 0; v < N; v += 1) {
if (zero_delay[u][v] <= S) {
dist[u][v] = zero_delay[u][v];
}
}
}
for (int st = 0; st < 80; st += 1) {
for (int w = 0; w < N; w += 1) {
for (int u = 0; u < N; u += 1) {
for (int v = 0; v < N; v += 1) {
dist[u][v] = min(dist[u][v], dist[u][w] + (dist[u][w] == 0 ? 0 : S - dist[u][w] % S) + zero_delay[w][v]);
}
}
}
}
vector<ll> sol(Q);
for (int i = 0; i < Q; i += 1) {
ll ans = 1e18;
ans = S - T[i] + dist[U[i]][V[i]];
for (int w = 0; w < N; w += 1) {
for (auto [time, extend] : paths[U[i]][w]) {
if (extend >= T[i]) {
if (w == V[i]) {
ans = min(ans, time);
} else {
ans = min(ans, S - T[i] + dist[w][V[i]]);
}
}
}
}
sol[i] = ans;
}
return sol;
}
