#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); // 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];
}
// static long long distE[10000][91];
// for (int ie = 0; ie < (int)es.size(); ie++) {
// int s = es[ie].v;
// cout << s << " start\n";
// vector<long long> dist(N, 1e18); dist[s] = es[ie].d;
// set<pair<long long, long long>> dijk; dijk.insert({es[ie].d, s});
// 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});
// }
// }
// }
// cout << "done\n";
// cout << ie << '\n';
// for (auto &x : dist) cout << x << '\n';
// for (int j = 0; j < N; j++) distE[ie][j] = dist[j];
// cout << distE[ie][0] << '\n';
// }
// 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;
}
// cout << x.second + S - (x.second + t) << " to refill then " << dist0[x.first][v] << '\n';
curans = min(curans, x.second + S - (x.second + t) + dist0[x.first][v]);
// 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 = distE[e.i][v];
// long long md = S - (a+t) + e.d;
// curans = min(curans, a + b + md);
// cout << a << " no reset\n";
// cout << md << " intermd\n";
// cout << b << " final\n";
// }
}
// cout << "done\n";
ans[i] = curans;
}
return ans;
}
