#include "escape_route.h"
#include <bits/stdc++.h>
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
using namespace std;
const long long INF=0x7f7f7f7f7f7f7f7fLL;
vector<tuple<long long,int,int>> qry[91];
long long CC[91][91], LL[91][91], D[91], PV[91];
int L[92], R[92], P[91];
void dijk(int N, long long S, int r, long long B)
{
memset(PV,0x7f,sizeof(PV));
memset(D,0x7f,sizeof(D));
D[r]=B;
R[0]=1; L[N+1]=N;
for(int i=1;i<=N;i++) {
L[i]=i-1;
R[i]=i+1;
}
P[r]=r;
for(int t=0;t<N;t++) {
long long mx=INF;
int c=r;
for(int j=R[0];j<=N;j=R[j]) if(mx>D[j]) {
mx=D[j];
c=j;
}
L[R[c]]=L[c];
R[L[c]]=R[c];
PV[c]=min(PV[c],PV[P[c]]);
for(int j=R[0];j<=N;j=R[j]) if(CC[c][j] && D[j]>(D[c]%S<=CC[c][j]-LL[c][j] ? D[c]:(D[c]+S-1)/S*S)+LL[c][j]) {
D[j]=(D[c]%S<=CC[c][j]-LL[c][j] ? D[c]:(D[c]+S-1)/S*S)+LL[c][j];
P[j]=c;
if(D[j]<S) PV[j]=CC[c][j]+1-LL[c][j]-D[c];
}
}
}
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)
{
vector<long long> ret(Q);
for(int i=0;i<M;i++) {
A[i]++; B[i]++;
LL[A[i]][B[i]]=LL[B[i]][A[i]]=L[i];
CC[A[i]][B[i]]=CC[B[i]][A[i]]=C[i];
}
for(int i=0;i<Q;i++) qry[++U[i]].emplace_back(T[i],++V[i],i);
for(int r=1;r<=N;r++) {
long long BB=0;
dijk(N,S,r,0);
sort(qry[r].rbegin(),qry[r].rend());
while(qry[r].size()) {
auto[t,v,i]=qry[r].back();
qry[r].pop_back();
if(t>=BB+PV[v]) dijk(N,S,r,BB=t);
ret[i]=D[v]-(D[v]<S ? BB:t);
}
}
return ret;
}
