#include "escape_route.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll INF=1e18+7;
const int LIM=107;
pair<ll,ll>T[LIM][LIM];
vector<vector<ll>>X[LIM];
vector<ll>P[LIM], K[LIM];
ll li[LIM], n, S, q;
void calc1() {
rep(i, n) {
rep(j, n) P[i].pb(INF);
vector<ll>odw(n);
P[i][i]=0;
while(true) {
pair<ll,ll>mi={INF, INF};
rep(j, n) if(!odw[j]) mi=min(mi, {P[i][j], j});
if(mi.st==INF) break;
ll p=mi.nd;
odw[p]=1;
rep(j, n) if(!odw[j] && T[p][j].nd!=-1) {
ll a=mi.st/S, b=mi.st%S;
if(b<=T[p][j].nd-T[p][j].st) P[i][j]=min(P[i][j], mi.st+T[p][j].st);
else P[i][j]=min(P[i][j], (a+1)*S+T[p][j].st);
}
}
}
}
vector<ll>calc2(ll a, ll b) {
vector<ll>odl(n, INF), odw(n);
odl[a]=0;
while(true) {
pair<ll,ll>mi={INF, INF};
rep(i, n) if(!odw[i]) mi=min(mi, {odl[i], i});
if(mi.st==INF) break;
ll p=mi.nd;
odw[p]=1;
rep(i, n) if(!odw[i] && T[p][i].nd!=-1) {
if(mi.st+b<=T[p][i].nd-T[p][i].st) odl[i]=min(odl[i], mi.st+T[p][i].st);
}
}
return odl;
}
vector<ll>calculate_necessary_time(int _n, int _m, ll _S, int _q, vector<int>_A, vector<int>_B,
vector<ll>_L, vector<ll>_C, vector<int>_U, vector<int>_V, vector<ll>_T) {
n=_n; S=_S; q=_q;
rep(i, n) rep(j, n) T[i][j]={0, -1};
rep(i, _m) T[_A[i]][_B[i]]=T[_B[i]][_A[i]]={_L[i], _C[i]};
calc1();
rep(i, n) {
X[i].pb(calc2(i, 0));
K[i].pb(0);
while(true) {
ll s=K[i].size()-1, nxt=INF;
rep(a, n) rep(b, n) if(X[i][s][a]+K[i][s]<=T[a][b].nd-T[a][b].st) {
nxt=min(nxt, T[a][b].nd-T[a][b].st-X[i][s][a]-K[i][s]);
}
nxt+=K[i][s]+1;
if(nxt>=INF) break;
X[i].pb(calc2(i, nxt));
K[i].pb(nxt);
}
rep(j, X[i].size()) {
rep(l, n) if(X[i][j][l]==INF) X[i][j][l]=2*INF;
rep(l, n) if(X[i][j][l]<INF) {
rep(d, n) X[i][j][d]=min(X[i][j][d], INF+S+P[l][d]);
}
}
}
vector<ll>ans(q, INF);
vector<pair<ll,ll>>pyt(q);
rep(i, q) pyt[i]={_T[i], i};
sort(all(pyt));
for(auto xd : pyt) {
int i=xd.nd;
ll a=_U[i], b=_V[i], c=_T[i];
while(li[a]+1<K[a].size() && K[a][li[a]+1]<=c) {
++li[a];
}
ll po=li[a];
if(X[a][po][b]<INF) {
ans[i]=X[a][po][b];
continue;
}
ans[i]=X[a][po][b]-INF-c;
}
return ans;
}
