#include "escape_route.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 4e18;
pair<ll, ll> adj[101][101];
int n, m, q, idx[101][9090];
ll MOD, dist0[101][101], dist[101][101][9090], sz[101];
pair<ll, int> ran[101][9090];
vector<pair<ll, int>> DB[101][101];
bool visited[101];
vector<ll> ans;
void dijkstra(int s, ll t, ll dist[], bool is0){
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[]){
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 = -INF, 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;
//printf("\n %d %d (Enum = %d)\n", x, y, Enum);
for (int i=1;i<=n;i++) if (distx[i] > -INF){
ran[i][sz[i]] = {distx[i]+1, Enum};
++sz[i];
for (int j=1;j<=n;j++) if (distx[i] > -INF && disty[j] < INF){
//printf(" %d -> %d: %lld -> %lld\n", i, j, distx[i], disty[j]);
DB[i][j].emplace_back(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++){
//printf("\n%d %d\n", s, v);
fill(dist[s][v], dist[s][v]+sz[s]+1, INF);
for (auto &[d, e]:DB[s][v]){
//printf(" %lld %d(->%d)\n", d, e, idx[s][e]);
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]);
//printf("%lld ", dist[s][v][i]);
}
//printf("\n");
}
fill(dist[s][s], dist[s][s]+sz[s], 0);
}
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);
for (int i=0;i<q;i++){
++U[i], ++V[i];
int pt = upper_bound(ran[U[i]], ran[U[i]]+sz[U[i]], make_pair(T[i], (int)1e9)) - ran[U[i]] - 1;
//printf(" %d %d %lld -> %d\n", U[i], V[i], T[i], pt);
ll ret = dist[U[i]][V[i]][pt];
for (int j=1;j<=n;j++) if (dist[U[i]][j][pt]<INF){
ret = min(ret, MOD - T[i] + dist0[j][V[i]]);
}
ans.push_back(ret);
}
return ans;
}
