#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 90 + 7;
const ll inf = 1e18;
int n;
vector<array<ll, 3>> g[N];
ll zero_delay[N][N], dist[N][N];
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) {
for (int i = 0; i < M; ++i) {
g[A[i]].push_back({B[i], L[i], C[i]});
g[B[i]].push_back({A[i], L[i], C[i]});
}
for (int u = 0; u < N; ++u) {
for (int v = 0; v < N; ++v) {
zero_delay[u][v] = inf;
}
vector<bool> vis(N);
priority_queue<pair<ll, int>> pq;
pq.push({0, u});
zero_delay[u][u] = 0;
while (!pq.empty()) {
int x = pq.top().second;
pq.pop();
if (vis[x]) continue;
vis[x] = 1;
for (auto [v, l, c] : g[x]) {
if (zero_delay[u][x] + l <= c && zero_delay[u][x] + l <= zero_delay[u][v]) {
zero_delay[u][v] = zero_delay[u][x] + l;
pq.push({-zero_delay[u][v], v});
}
}
}
}
for (int u = 0; u < N; ++u) {
for (int v = 0; v < N; ++v) {
dist[u][v] = zero_delay[u][v];
}
}
for (int step = 0; step < 100; ++step) {
for (int w = 0; w < N; ++w) {
for (int u = 0; u < N; ++u) {
for (int v = 0; v < N; ++v) {
dist[u][v] = min(dist[u][v], dist[u][w] + S - dist[u][w] % S + dist[w][v]);
}
}
}
}
vector<ll> sol(Q);
vector<ll> d(N);
vector<bool> u(N);
for (int i = 0; i < Q; ++i) {
for (int j = 0; j < N; ++j) {
d[j] = inf;
u[j] = 0;
}
d[U[i]] = 0;
for (int j = 0; j < N; ++j) {
int v = -1;
for (int k = 0; k < N; ++k) {
if (!u[k] && (v == -1 || d[k] < d[v])) {
v = k;
}
}
if (d[v] == inf) break;
u[v] = 1;
for (auto [to, l, c] : g[v]) {
if (T[i] + d[v] + l <= c && d[v] + l < d[to]) {
d[to] = d[v] + l;
}
}
}
ll ans = inf;
if (d[V[i]] != inf) {
ans = min(ans, d[V[i]]);
}
for (int w = 0; w < N; ++w) {
if (d[w] != inf) {
ans = min(ans, S - T[i] + dist[w][V[i]]);
}
}
sol[i] = ans;
}
return sol;
}
