#include "escape_route.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
const long long inf = 1000000000000000000;
#define N_MAX 90
#define M_MAX (N_MAX * (N_MAX - 1) / 2)
#define Q_MAX 3000000
class Path {
public:
long long l, c, d;
Path(): l(inf * 2), c(0), d(-inf * 2) {}
Path(long long _l, long long _c): l(_l), c(_c), d(_c - _l) {}
};
int n, m;
long long s;
Path ps[N_MAX][N_MAX];
tuple<int, int, Path> pl[M_MAX];
long long reach[N_MAX][N_MAX];
long long from0[N_MAX][N_MAX];
long long latest_first[N_MAX][M_MAX * 2];
long long latest_second[M_MAX * 2][N_MAX];
vector<pair<long long, int>> query[N_MAX][N_MAX];
int ql[Q_MAX];
vector<long long> answer;
long long require_time(Path p, long long t) {
t = t % s;
if(t <= p.d) {
return p.l;
} else {
return s + p.l - t;
}
}
long long require_time_oneday(Path p, long long t) {
if(t <= p.d) {
return p.l;
} else {
return inf;
}
}
long long require_time_oneday_reverse(Path p, long long t) {
if(t < p.l) {
return inf;
} else if(t > p.c) {
return t - p.d;
} else {
return p.l;
}
}
void prepare_overday_reverse(int x) {
vector<long long> z(n, -1);
vector<bool> un(n, true);
int now = x;
z[x] = s - 1;
while(now >= 0) {
un[now] = false;
long long nt = z[now];
int next = -1;
long long current = -1;
rep(i, n) {
if(un[i]) {
z[i] = max(z[i], nt - require_time_oneday_reverse(ps[now][i], nt));
if(current < z[i]) {
current = z[i];
next = i;
}
}
}
now = next;
}
rep(i, n) {
reach[i][x] = z[i];
}
}
void prepare_overday(int x) {
vector<long long> z(n, inf);
vector<bool> un(n, true);
int now = x;
z[x] = 0;
while(now >= 0) {
un[now] = false;
long long nt = z[now];
int next = -1;
long long current = inf;
rep(i, n) {
if(un[i]) {
z[i] = min(z[i], nt + require_time(ps[now][i], nt));
if(current > z[i]) {
current = z[i];
next = i;
}
}
}
now = next;
}
rep(i, n) {
from0[i][x] = z[i];
}
}
void prepare_overday() {
rep(i, n) {
prepare_overday_reverse(i);
prepare_overday(i);
}
}
void prepare_oneday_reverse(int x, long long t, int w) {
vector<long long> z(n, -1);
vector<bool> un(n, true);
int now = w;
z[w] = t;
while(now >= 0) {
un[now] = false;
long long nt = z[now];
int next = -1;
long long current = -1;
rep(i, n) {
if(un[i]) {
z[i] = max(z[i], nt - require_time_oneday_reverse(ps[now][i], nt));
if(current < z[i]) {
current = z[i];
next = i;
}
}
}
now = next;
}
rep(i, n) {
latest_first[i][x] = z[i];
}
}
void prepare_oneday(int x, long long t, int w) {
vector<long long> z(n, inf);
vector<bool> un(n, true);
int now = w;
z[w] = t;
while(now >= 0) {
un[now] = false;
long long nt = z[now];
int next = -1;
long long current = inf;
rep(i, n) {
if(un[i]) {
z[i] = min(z[i], nt + require_time_oneday(ps[now][i], nt));
if(current > z[i]) {
current = z[i];
next = i;
}
}
}
now = next;
}
rep(i, n) {
latest_second[x][i] = z[i];
}
}
void prepare_oneday() {
rep(i, m) {
prepare_oneday_reverse(i * 2, get<2>(pl[i]).c, get<0>(pl[i]));
prepare_oneday_reverse(i * 2 + 1, get<2>(pl[i]).c, get<1>(pl[i]));
prepare_oneday(i * 2, get<2>(pl[i]).c, get<0>(pl[i]));
prepare_oneday(i * 2 + 1, get<2>(pl[i]).c, get<1>(pl[i]));
}
}
void prepare() {
prepare_overday();
prepare_oneday();
}
void solve_overday(int u, int v) {
vector<pair<long long, long long>> w;
rep(i, n) {
if(reach[u][i] >= 0) {
w.push_back(make_pair(reach[u][i], from0[v][i]));
}
}
for(auto i: query[u][v]) {
w.push_back(make_pair(i.first, i.second - inf));
}
sort(w.begin(), w.end(), greater<pair<long long, long long>>());
long long now = inf;
for(auto i: w) {
if(i.second < 0) {
answer[i.second + inf] = min(answer[i.second + inf], s - i.first + now);
} else {
now = min(now, i.second);
}
}
for(auto i: w) {
if(i.second < 0) {
answer[i.second + inf] = min(answer[i.second + inf], s * 2 - i.first + now);
}
}
}
void solve_oneday(int u) {
vector<pair<long long, long long>> w;
rep(i, m * 2) {
if(latest_first[u][i] >= 0) {
w.push_back(make_pair(latest_first[u][i], i));
}
}
rep(i, n) {
for(auto j: query[u][i]) {
w.push_back(make_pair(j.first, j.second - inf));
}
}
sort(w.begin(), w.end(), greater<pair<long long, long long>>());
vector<long long> now(n, inf);
for(auto i: w) {
if(i.second < 0) {
int idx = i.second + inf;
answer[idx] = min(answer[idx], now[ql[idx]]);
} else {
rep(j, n) {
now[j] = min(now[j], latest_second[i.second][j] - i.first);
}
}
}
for(auto i: w) {
if(i.second < 0) {
int idx = i.second + inf;
answer[idx] = min(answer[idx], s - i.first + now[ql[idx]]);
}
}
}
void solve(int q) {
answer.resize(q, inf);
rep(i, n) {
rep(j, n) {
if(i != j) {
solve_overday(i, j);
}
}
}
rep(i, n) {
solve_oneday(i);
}
}
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, vector<int> U,
vector<int> V, vector<long long> T) {
n = N;
m = M;
s = S;
rep(i, m) {
Path p(L[i], C[i]);
ps[A[i]][B[i]] = p;
ps[B[i]][A[i]] = p;
pl[i] = make_tuple(A[i], B[i], p);
}
rep(i, Q) {
query[U[i]][V[i]].push_back(make_pair(T[i], i));
ql[i] = V[i];
}
prepare();
solve(Q);
return answer;
}
