#include "escape_route.h"
using namespace std;
#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
// #define int long long
struct edge {
long long to, d, c, i;
};
struct edges {
long long u, v, d, c;
};
std::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, std::vector<int> U, std::vector<int> V, std::vector<long long> T) {
vector<vector<edge>> adj(N);
vector<edges> es;
int eid = 0;
for (int i = 0; i < M; i++) {
long long u, v, d, c;
u = A[i]; v = B[i]; d = L[i]; c = C[i];
es.pb({u, v, d, c});
adj[u].pb({v, d, c, eid});
eid++;
es.pb({v, u, d, c});
adj[v].pb({u, d, c, eid});
}
vector<map<long long, vector<pair<long long, long long>>>> mpp(N);
for (int NODE = 0; NODE < N; NODE++) {
long long bn = 0;
while (true) {
long long wrst = (long long)1e18;
vector<long long> dist(N, (long long)1e18);
vector<bool> vis(N, false);
dist[NODE] = bn;
for (int it2 = 0; it2 < N; it2++) {
int node = -1;
long long best = (long long)1e18;
for (int j = 0; j < N; j++) {
if (!vis[j] && dist[j] < best) {
best = dist[j];
node = j;
}
}
if (node == -1) break;
vis[node] = true;
long long curd = dist[node];
for (auto &e : adj[node]) {
long long to = e.to, d = e.d, c = e.c;
long long aft;
long long gap = c - (curd + d);
if (gap >= 0) {
aft = d;
if (aft + curd < dist[to]) {
dist[to] = aft + curd;
wrst = min(wrst, gap);
}
}
}
}
vector<pair<long long, long long>> adds;
for (int i = 0; i < N; i++) {
if (dist[i] == (long long)1e18) continue;
adds.push_back({i, dist[i] - bn});
}
mpp[NODE][bn] = adds;
if (adds.size() <= 1) break;
bn += wrst + 1;
}
}
long long dist0[91][91];
for (int i = 0; i < N; i++) {
vector<long long> dist(N, (long long)1e18);
vector<bool> vis(N, false);
dist[i] = 0;
for (int it2 = 0; it2 < N; it2++) {
int node = -1;
long long best = (long long)1e18;
for (int j = 0; j < N; j++) {
if (!vis[j] && dist[j] < best) {
best = dist[j];
node = j;
}
}
if (node == -1) break;
vis[node] = true;
long long curd = dist[node];
for (auto &e : adj[node]) {
long long to = e.to, d = e.d, c = e.c;
long long aft;
if (curd % S + d <= c) aft = d;
else aft = d + S - curd % S;
if (aft + curd < dist[to]) {
dist[to] = aft + curd;
}
}
}
for (int j = 0; j < N; j++) dist0[i][j] = dist[j];
}
vector<long long> ans(Q, 0);
for (int i = 0; i < Q; i++) {
long long u, v, t;
u = U[i]; v = V[i]; t = T[i];
auto it = mpp[u].upper_bound(t); it--;
map<long long, long long> avail;
for (auto &x : it->second) avail[x.first] = x.second;
long long curans = (long long)1e18;
for (auto &x : avail) {
if (x.first == v) {
curans = x.second;
break;
}
curans = min(curans, x.second + S - (x.second + t) + dist0[x.first][v]);
}
ans[i] = curans;
}
return ans;
}
