#include "escape_route.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 4e18;
pair<ll, ll> adj[91][91];
int n, m, q, idx[91][8102];
ll MOD, dist0[91][91], dist[91][91][8102], sz[91], sz2[91][91];
pair<ll, int> ran[91][8102], DB[91][91][8102];
bool visited[91];
vector<ll> ans;
void dijkstra(int s, ll t, ll dist[], bool is0){
memset(dist, 0x3f, sizeof(ll)*(n+1));
memset(visited, 0, sizeof(visited));
//fill(dist+1, dist+n+1, INF);
//fill(visited+1, visited+n+1, 0);
dist[s] = t;
for (int i=1;i<=n;i++){
ll mn = INF, v = -1;
for (int j=1;j<=n;j++) if (!visited[j] && mn > dist[j]) mn = dist[j], v = j;
if (v==-1) break;
visited[v] = 1;
//printf(" %d %lld\n", v, mn);
for (int nxt=1;nxt<=n;nxt++) if (!visited[nxt] && adj[v][nxt].first){
auto &[l, c] = adj[v][nxt];
ll nt = mn + l;
if (!is0){
if (mn>c-l) continue;
}
else if (mn%MOD > c-l){
nt = (mn/MOD*MOD + MOD) + l;
}
if (nt < dist[nxt]){
dist[nxt] = nt;
}
}
}
}
void dijkINV(int s, ll t, ll dist[]){
memset(dist, -1, sizeof(ll)*(n+1));
memset(visited, 0, sizeof(visited));
//fill(dist+1, dist+n+1, -INF);
//fill(visited+1, visited+n+1, 0);
dist[s] = t;
for (int i=1;i<=n;i++){
ll mx = -1, v = -1;
for (int j=1;j<=n;j++) if (!visited[j] && mx < dist[j]) mx = dist[j], v = j;
if (v==-1) break;
visited[v] = 1;
for (int nxt=1;nxt<=n;nxt++) if (!visited[nxt] && adj[v][nxt].first){
auto &[l, c] = adj[v][nxt];
ll nt = mx - l;
if (nt > c-l) continue;
if (nt > dist[nxt]){
dist[nxt] = nt;
}
}
}
}
ll distx[101], disty[101];
int Enum;
void calc(int x, int y){
if (!adj[x][y].first) return;
auto [l, c] = adj[x][y];
dijkINV(x, c-l, distx);
dijkstra(y, c, disty, 0);
++Enum;
for (int i=1;i<=n;i++) if (distx[i] > -1){
ran[i][sz[i]++] = {distx[i]+1, Enum};
for (int j=1;j<=n;j++) if (distx[i] > -1 && disty[j] < INF){
DB[i][j][sz2[i][j]++] = {disty[j] - distx[i], Enum};
}
}
}
void init(int s){
sort(ran[s], ran[s]+sz[s]);
for (int i=1;i<sz[s];i++) idx[s][ran[s][i].second] = i;
for (int v=1;v<=n;v++){
memset(dist[s][v], 0x3f, sizeof(ll)*(sz[s]+1));
//fill(dist[s][v], dist[s][v]+sz[s]+1, INF);
for (int i=0;i<sz2[s][v];i++){
auto &[d, e] = DB[s][v][i];
dist[s][v][idx[s][e]-1] = d;
}
for (int i=sz[s]-1;i>=0;i--){
dist[s][v][i] = min(dist[s][v][i], dist[s][v][i+1]);
}
}
memset(dist[s][s], 0, sizeof(ll)*(sz[s]+1));
//fill(dist[s][s], dist[s][s]+sz[s], 0);
}
struct FUCK{
int u, v, i;
ll t;
FUCK(){}
FUCK(int _u, int _v, ll _t, int _i): u(_u), v(_v), i(_i), t(_t) {}
bool operator<(const FUCK &FUUUUUCK) const{
return tie(u, t) < tie(FUUUUUCK.u, FUUUUUCK.t);
}
}fuck[3003000];
int fuuck[101];
std::vector<long long> calculate_necessary_time(
int N, int M, long long S, int Q, std::vector<int> A, std::vector<int> B,
std::vector<long long> L, std::vector<long long> C, std::vector<int> U,
std::vector<int> V, std::vector<long long> T) {
n = N, m = M, MOD = S, q = Q;
for (int i=0;i<m;i++){
++A[i], ++B[i];
adj[A[i]][B[i]] = make_pair(L[i], C[i]);
adj[B[i]][A[i]] = make_pair(L[i], C[i]);
}
for (int i=1;i<=n;i++) dijkstra(i, 0, dist0[i], 1);
fill(sz+1, sz+n+1, 1);
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++) calc(i, j);
}
for (int i=1;i<=n;i++) init(i);
//if (n>60) exit(0);
for (int i=0;i<q;i++) fuck[i] = FUCK(U[i]+1, V[i]+1, T[i], i);
sort(fuck, fuck+q);
ans.resize(q);
for (int i=0;i<q;i++){
int u = fuck[i].u;
int v = fuck[i].v;
int ii = fuck[i].i;
ll t = fuck[i].t;
while(fuuck[u]<sz[u] && ran[u][fuuck[u]].first <= t) fuuck[u]++;
int pt = fuuck[u] - 1;
//printf(" %d %d %lld -> %d\n", U[i], V[i], T[i], pt);
ll ret = dist[u][v][pt];
for (int j=1;j<=n;j++) if (dist[u][j][pt]<INF){
ret = min(ret, MOD - t + dist0[j][v]);
}
ans[ii] = ret;
}
return ans;
}
