#include<bits/stdc++.h>
using ll = long long;
std::vector<ll> calculate_necessary_time(int n, int m, ll s, int q, std::vector<int> a, std::vector<int> b, std::vector<ll> l, std::vector<ll> c, std::vector<int> u, std::vector<int> v, std::vector<ll> t) {
std::vector<std::vector<std::tuple<int, ll, ll>>> adj(n);
for (int i = 0; i < m; ++i) {
adj[a[i]].emplace_back(b[i], l[i], c[i]);
adj[b[i]].emplace_back(a[i], l[i], c[i]);
}
auto dijkstra = [&](int u, ll t) -> std::vector<ll> {
std::vector<ll> dp(n, 1e18);
std::vector<bool> used(n, false);
dp[u] = t;
for (int iter = 0; iter < n; ++iter) {
int u = -1;
for (int v = 0; v < n; ++v) {
if (!used[v] && (u == -1 || dp[v] < dp[u])) u = v;
}
used[u] = true;
for (auto [to, l, c] : adj[u]) {
if (dp[u] % s <= c - l) {
dp[to] = std::min(dp[to], dp[u] + l);
} else {
dp[to] = std::min(dp[to], dp[u] + s - dp[u] % s + l);
}
}
}
return dp;
};
std::vector<ll> ans(q);
for (int i = 0; i < q; ++i) {
ans[i] = dijkstra(u[i], t[i])[v[i]] - t[i];
}
return ans;
}
