#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 S = 4000;
const int Q = 3'000'000;
const ll INF = 1'000'000'000'000'000'000;
int n, m, q;
ll l[N + 10], c[N + 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];
void calcDisType1(int r, ll timSt) {
for (int i = 1; i <= n; i++)
d[i] = INF;
set<pair<ll, int>> st;
st.insert({0, r});
d[r] = 0;
tim[r] = timSt;
while (!st.empty()) {
int u = st.begin() -> second;
st.erase(st.begin());
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]) {
st.erase({d[v], v});
d[v] = newDis;
tim[v] = newTim;
st.insert({d[v], v});
}
}
}
}
void solve() {
for (int i = 1; i <= q; i++) {
calcDisType1(x[i], t[i]);
ans[i] = d[y[i]];
}
}
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];
}
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 << ' ';
cout << endl;
return 0;
}*/
