#include "escape_route.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define BIT(mask,i) (((mask) >> (i))&1LL)
#define MASK(i) (1LL << (i))
#define MP make_pair
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
namespace{
const ll MAXN = 90;
const ll INF = 1e18;
ll n,m,s,q;
ll c[MAXN+10][MAXN+10],l[MAXN+10][MAXN+10];
ll st[MAXN+10][MAXN+10][MAXN+10],en[MAXN+10][MAXN+10][MAXN+10];
ll pre[MAXN+10][MAXN+10];
bool used[MAXN+10];
ll dist[MAXN+10];
ll last_c[MAXN+10];
struct query{
ll u,v,t,id;
};
vector <query> all_query;
vector <ll> ans;
void solve(){
ans.resize(sz(all_query));
sort(all_query.begin(),all_query.end(),[&](query x,query y){return x.u < y.u;});
for (ll i = 1;i <= n;i ++){
for (ll j = 1;j <= n;j ++){dist[j] = INF;used[j] = 0;}
dist[i] = 0;
for (ll z = 1;z <= n;z ++){
ll u = 0;
for (ll j = 1;j <= n;j ++){
if (!used[j] && (!u || dist[j] < dist[u]))u=j;
}
used[u] = 1;
for (ll v = 1;v <= n;v ++){
if (used[v])continue;
if (c[u][v] == 0)continue;
ll x = dist[u]%s;
ll w;
if (x + l[u][v] > c[u][v])w = dist[u]+s-x+l[u][v];
else w = dist[u]+l[u][v];
dist[v] = min(dist[v],w);
}
}
for (ll j = 1;j <= n;j ++)pre[i][j] = dist[j];
}
for (ll i = 1;i <= n;i ++){
for (ll k = 1;k <= n;k ++){
for (ll j = 1;j <= n;j ++){dist[j] = INF;used[j] = 0;}
dist[i] = c[i][k];
for (ll z = 1;z <= n;z ++){
ll u = 0;
for (ll j = 1;j <= n;j ++){
if (!used[j] && (!u || dist[j] < dist[u]))u=j;
}
used[u] = 1;
for (ll v = 1;v <= n;v ++){
if (used[v])continue;
if (c[u][v] == 0)continue;
if (dist[u] + l[u][v] <= min(c[u][v],dist[v]))dist[v] = dist[u] + l[u][v];
}
}
for (ll j = 1;j <= n;j ++)en[i][k][j] = dist[j];
}
}
for (ll i = 1;i <= n;i ++){
for (ll k = 1;k <= n;k ++){
for (ll j = 1;j <= n;j ++){dist[j] = -INF;used[j] = 0;}
dist[i] = c[i][k];
for (ll z = 1;z <= n;z ++){
ll u = 0;
for (ll j = 1;j <= n;j ++){
if (!used[j] && (!u || dist[j] > dist[u]))u=j;
}
used[u] = 1;
for (ll v = 1;v <= n;v ++){
if (used[v])continue;
if (c[u][v] == 0)continue;
if (min(dist[u],c[u][v]) - l[u][v] >= max(0LL,dist[v]))dist[v] = min(dist[u],c[u][v]) - l[u][v];
}
}
for (ll j = 1;j <= n;j ++)st[i][k][j] = dist[j];
}
}
sort(all_query.begin(),all_query.end(),[&](query x,query y){
if (x.u != y.u)return x.u<y.u;
else return x.t > y.t;
});
for (ll i = 1,ptr1 = 0;i <= n;i ++){
vector <pair <ll,pll > > pos;
for (ll j = 1;j <= n;j ++){
for (ll k = 1;k <= n;k ++){
if (st[j][k][i] >= 0){
pos.push_back(MP(st[j][k][i],MP(j,k)));
}
}
}
sort(pos.begin(),pos.end(),[&](pair <ll,pll > x, pair <ll,pll > y){return x.fi > y.fi;});
for (ll j = 1;j <= n;j ++){
dist[j] = INF;
}
dist[i]=0;
ll ptr2 = 0;
for (;ptr1 < sz(all_query) && all_query[ptr1].u==i;ptr1++){
// cout<<ptr1<<endl;
for (;ptr2 < sz(pos) && pos[ptr2].fi >= all_query[ptr1].t;ptr2++){
for (ll j = 1;j <= n;j ++){
if (en[pos[ptr2].se.fi][pos[ptr2].se.se][j] != INF){
dist[j] = min(dist[j],en[pos[ptr2].se.fi][pos[ptr2].se.se][j]-st[pos[ptr2].se.fi][pos[ptr2].se.se][i]);
}
}
}
if (dist[all_query[ptr1].v]!=INF)ans[all_query[ptr1].id] = dist[all_query[ptr1].v];
else {
ans[all_query[ptr1].id] = INF;
for (ll j = 1;j <= n;j ++){
if (dist[j] != INF)ans[all_query[ptr1].id] = min(ans[all_query[ptr1].id],pre[j][all_query[ptr1].v]+s-all_query[ptr1].t);
}
}
}
}
}
}
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,s = S,q = Q;
for (ll i = 1;i <= n;i ++){
for (ll j = 1;j <= n;j ++){
c[i][j] = 0;
l[i][j] = 1;
}
}
for (ll i = 0;i < m;i ++){
ll u,v;
u = A[i]+1,v = B[i]+1;
c[u][v] = c[v][u] = C[i];
l[u][v] = l[v][u] = L[i];
}
for (ll i = 0;i < q;i ++){
all_query.push_back({U[i]+1,V[i]+1,T[i],i});
}
solve();
return ans;
}
