#include <bits/stdc++.h>
using namespace std;
const int64_t inf = 1e17;
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) {
#define int int64_t
vector<vector<pair<int, int>>> adj(N);
for (int i = 0; i < M; ++i) {
adj[A[i]].push_back({B[i], i});
adj[B[i]].push_back({A[i], i});
}
auto solve_from_0 = [&](int u, int t) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({t, u});
vector<bool> vis(N);
vector<int> ans(N);
while (!pq.empty()) {
auto [t, u] = pq.top();
pq.pop();
if (vis[u]) {
continue;
}
vis[u] = true;
ans[u] = t;
for (auto &[i, idx] : adj[u]) {
int l = L[idx];
if ((t % S) <= C[idx] - l) {
pq.push({t + l, i});
} else {
pq.push({(t / S) * S + S + l, i});
}
}
}
return ans;
};
vector ans_from_0(N, vector<int>(N));
for (int i = 0; i < N; ++i) {
ans_from_0[i] = solve_from_0(i, 0);
}
auto solve = [&](int u, int v, int t) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({t, u});
vector<bool> vis(N);
int ans = inf;
while (!pq.empty()) {
auto [t, u] = pq.top();
pq.pop();
if (vis[u]) {
continue;
}
vis[u] = true;
if (u == v) {
return min(ans, t);
}
for (auto &[i, idx] : adj[u]) {
int l = L[idx];
if (t <= C[idx] - l) {
pq.push({t + l, i});
} else {
ans = min(ans, int64_t(ans_from_0[u][v] + S));
}
}
}
return ans;
};
vector<long long> ans(Q);
for (int i = 0; i < Q; ++i) {
ans[i] = solve(U[i], V[i], T[i]) - T[i];
}
#undef int
return ans;
}
