#pragma GCC optimize("O2,unroll-loops,Ofast")
#include "escape_route.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vii;
typedef vector<ll> vll;
const int N = 90;
const int M = N * N / 2;
const int S = 8100;
const int Q = 3'000'000;
const ll INF = 1'000'000'000'000'000'000;
int n, m, q, ed[N + 10][N + 10];
int par[N + 10], parE[N + 10];
ll l[M + 10], c[M + 10], s;
ll x[Q + 10], y[Q + 10], t[Q + 10], ans[Q + 10];
ll dis0[N + 10][N + 10], mxT[N + 10][N + 10];
ll dis[N + 10][S + 10][N + 10];
ll d[N + 10], tim[N + 10];
vector<ll> imp[N + 10];
vector<pair<int, int>> adj[N + 10];
vector<int> vec, remain;
bool mark[N + 10];
int pntSt, lst[N + 10], nxt[N + 10];
int see[N + 10];
void calcDisType1(int r, ll timSt) {
for (int i = 1; i <= n; i++)
d[i] = INF;
priority_queue<pair<ll, int>> st;
st.push({0, r});
d[r] = 0;
tim[r] = timSt;
while (!st.empty()) {
int u = st.top().second;
ll last = -st.top().first;
st.pop();
if (last != d[u])
continue;
for (auto [v, e]: adj[u]) {
ll newDis = d[v], newTim;
if (tim[u] <= c[e]) {
if (d[u] + l[e] < d[v]) {
newDis = d[u] + l[e];
newTim = tim[u] + l[e];
}
}
else if (d[u] + s - tim[u] + l[e] < d[v]) {
newDis = d[u] + s - tim[u] + l[e];
newTim = l[e];
}
if (newDis < d[v]) {
d[v] = newDis;
tim[v] = newTim;
st.push({-d[v], v});
}
}
}
}
void del(int u) {
if (pntSt == u)
pntSt = nxt[u];
int x = lst[u], y = nxt[u];
if (x)
nxt[x] = y;
if (y)
lst[y] = x;
}
void calcDisType2(int r, ll timSt, bool use = true) {
fill(see + 1, see + n + 1, false);
for (int i = 1; i <= n; i++)
if (!mark[i]){
d[i] = INF;
par[i] = 0;
}
d[r] = 0;
tim[r] = timSt;
while (true) {
int u = 0;
for (int i = 1; i <= n; i++)
if (!see[i] && d[i] != INF && (u == 0 || d[i] < d[u]))
u = i;
if (!u)
break;
see[u] = true;
for (auto [v, e]: adj[u])
if (tim[u] <= c[e] && d[u] + l[e] < d[v]) {
d[v] = d[u] + l[e];
tim[v] = tim[u] + l[e];
par[v] = u;
parE[v] = e;
}
}
}
void calcDis0() {
for (int i = 1; i <= n; i++) {
calcDisType1(i, 0);
for (int j = 1; j <= n; j++)
dis0[i][j] = d[j];
}
}
void calcDis(int u) {
imp[u].push_back(0);
calcDisType2(u, 0, false);
for (int i = 1; i <= n; i++)
dis[u][0][i] = d[i];
int pnt = 0;
while (true) {
ll mn = INF;
for (int i = 1; i <= n; i++)
if (par[i])
mn = min(mn, c[parE[i]] - (imp[u].back() + d[par[i]]));
if (mn == INF)
break;
ll tmp = imp[u].back() + mn + 1;
calcDisType2(u, tmp);
pnt++;
for (int v = 1; v <= n; v++)
dis[u][pnt][v] = d[v];
imp[u].push_back(tmp);
}
}
void calcDis() {
for (int i = 1; i <= n; i++)
calcDis(i);
}
void calcMxT() {
for (int i = 1; i <= n; i++) {
mxT[i][i] = s;
for (int j = 1; j <= n; j++)
if (j != i) {
mxT[i][j] = -1;
for (int pnt = 0; pnt < (int) imp[i].size(); pnt++)
if (dis[i][pnt][j] != INF)
mxT[i][j] = (pnt + 1 == imp[i].size()? s - 1: imp[i][pnt + 1] - 1);
}
}
}
void calcAns() {
for (int i = 1; i <= q; i++) {
int u = x[i], v = y[i];
int idx = upper_bound(imp[u].begin(), imp[u].end(), t[i]) - imp[u].begin();
ans[i] = dis[u][idx - 1][v];
for (int mid = 1; mid <= n; mid++)
if (t[i] <= mxT[u][mid])
ans[i] = min(ans[i], s - t[i] + dis0[mid][v]);
}
}
void solve() {
calcDis0();
calcDis();
calcMxT();
calcAns();
}
vll writeOutput() {
vll res;
for (int i = 1; i <= q; i++)
res.push_back(ans[i]);
return res;
}
vll calculate_necessary_time(int N, int M, ll S, int Q, vii A, vii B, vll L, vll C, vii U, vii V, vll T) {
n = N;
m = M;
s = S;
q = Q;
for (int i = 0; i < m; i++) {
int u = A[i] + 1, v = B[i] + 1;
adj[u].push_back({v, i + 1});
adj[v].push_back({u, i + 1});
l[i + 1] = L[i];
c[i + 1] = C[i] - L[i];
ed[u][v] = ed[v][u] = i + 1;
}
for (int i = 0; i < q; i++) {
x[i + 1] = U[i] + 1;
y[i + 1] = V[i] + 1;
t[i + 1] = T[i];
}
solve();
return writeOutput();
}
/*int main() {
int n, m;
ll s;
int q;
vii A, B, U, V;
vll L, C, T;
cin >> n >> m >> s >> q;
for (int i = 1; i <= m; i++) {
int x, y;
ll z, t;
cin >> x >> y >> z >> t;
A.push_back(x);
B.push_back(y);
L.push_back(z);
C.push_back(t);
}
int Q = q;
U.resize(Q);
V.resize(Q);
T.resize(Q);
for (int i = 0; i < q; i++)
cin >> U[i] >> V[i] >> T[i];
vll ans = calculate_necessary_time(n, m, s, q, A, B, L, C, U, V, T);
for (auto x: ans)
cout << x << endl;
return 0;
} */
