#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;
};
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);
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];
adj[u].pb({v, d, c});
adj[v].pb({u, d, c});
}
vector<map<long long, vector<pair<long long, long long>>>> mpp(N); // mpp[node][dist] gives dijkstra dist array visitable without any resets
for (int NODE = 0; NODE < N; NODE++) {
long long bn = 0; // bottleneck
// cout << "NODE " << NODE << '\n';
while (true) {
// do dijk with bottleneck
long long wrst = 1e18;
// cout << "starting with " << bn << '\n';
vector<long long> dist(N, 1e18); dist[NODE] = bn;
set<pair<long long, long long>> dijk; dijk.insert({bn, NODE});
while (dijk.size()) {
auto cur = *dijk.begin();
dijk.erase(dijk.begin());
long long curd = cur.first; long long node = cur.second;
if (dist[node] < curd) continue;
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) {
// this works
aft = d;
if (aft+curd < dist[to]) {
dijk.erase({dist[to], to});
dist[to] = aft + curd;
dijk.insert({dist[to], to});
wrst = min(wrst, gap);
}
}
}
}
vector<pair<long long, long long>> adds;
for (int i = 0; i < N; i++) {
if (dist[i] == 1e18) continue;
adds.push_back({i, dist[i] - bn});
// cout << i << " reachable\n";
}
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, 1e18); dist[i] = 0;
set<pair<long long, long long>> dijk; dijk.insert({0, i});
while (dijk.size()) {
auto cur = *dijk.begin();
dijk.erase(dijk.begin());
long long curd = cur.first; int node = cur.second;
if (dist[node] < curd) continue;
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]) {
dijk.erase({dist[to], to});
dist[to] = aft + curd;
dijk.insert({dist[to], to});
}
}
}
for (int j = 0; j < N; j++) dist0[i][j] = dist[j];
}
// for (int i = 0; i < N; i++) {
// for (int j = 0; j < N; j++) cout << dist0[i][j] << " ";
// cout << '\n';
// }
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];
// cout << "Q: " << u << " " << v << " " << t << '\n';
auto it = mpp[u].upper_bound(t); it--;
// cout << "mpp:\n";
// for (auto &mm : mpp[u]) cout << mm.first << '\n';
// if ((mpp[u].rbegin())->first <= t) {
// it = mpp[u].end();
// // it--;
// }
// cout << it->first << " is the most recent change\n";
map<long long, long long> avail; for (auto &x : it->second) avail[x.first] = x.second;
long long curans = 1e18;
for (auto &x : avail) {
// cout << x.first << " node with " << x.second << " dist is reacahble\n";
if (x.first == v) {
// cout << "oh lmfao\n";
curans = x.second;
break;
}
// thjis is boundary
for (auto &e : adj[x.first]) {
int to = e.to;
if (avail.count(to) > 0) continue;
// cout << "till here no reset then " << to << " i reset\n";
long long a = x.second;
long long b = dist0[to][v];
long long md = S - (a+t) + e.d;
curans = min(curans, a + b + md);
// cout << a << " no reset " << md << " reset time " << b << " final\n";
}
}
ans[i] = curans;
}
return ans;
}
