#include "escape_route.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);s<e?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll n,m,s,q;
struct edge{
ll to;
ll w;
ll leave;
};
vector<edge> al[95];
ll w[95][4105][95]; //(u,time,v) go from u to v at t=time
vector<ll> t[95]; //the important times
ll w2[95][95]; //(u,time,v) if you start u at time 0
bool proc[95];
ll dw[95];
ii dw2[95];
std::vector<ll> calculate_necessary_time(
int N, int M, ll S, int Q, std::vector<int> A, std::vector<int> B,
std::vector<ll> L, std::vector<ll> C, std::vector<int> U,
std::vector<int> V, std::vector<ll> T) {
n=N,m=M,s=S,q=Q;
rep(x,0,m){
al[A[x]].pub(edge({B[x],L[x],C[x]-L[x]}));
al[B[x]].pub(edge({A[x],L[x],C[x]-L[x]}));
}
rep(x,0,n) sort(all(al[x]),[](edge &i,edge &j){
return i.leave>j.leave;
});
rep(x,0,n){
memset(dw2,63,sizeof(dw2));
memset(proc,false,sizeof(proc));
dw2[x]=ii(0,0);
rep(y,0,n){
ll curr=-1;
rep(z,0,n) if (!proc[z] && (curr==-1 || dw2[z]<dw2[curr])) curr=z;
proc[curr]=true;
for (auto &it:al[curr]){
ii temp=dw2[curr];
if (temp.se<=it.leave) temp.se+=it.w;
else temp=ii(temp.fi+1,it.w);
dw2[it.to]=min(dw2[it.to],temp);
}
}
rep(y,0,n) w2[x][y]=dw2[y].fi*s+dw2[y].se;
}
rep(x,0,n){
ll ctime=0;
int IDX=0;
while (true){
ll extra=1e18;
memset(dw,63,sizeof(dw));
memset(proc,false,sizeof(proc));
dw[x]=ctime;
rep(y,0,n){
ll curr=-1;
rep(z,0,n) if (!proc[z] && (curr==-1 || dw[z]<dw[curr])) curr=z;
if (dw[curr]>1e18) break;
proc[curr]=true;
for (auto &it:al[curr]){
ll temp=dw[curr];
if (temp<=it.leave){
if (dw[it.to]>temp+it.w) extra=min(extra,it.leave-temp);
temp+=it.w;
}
else break;
dw[it.to]=min(dw[it.to],temp);
}
}
t[x].pub(ctime);
rep(y,0,n) w[x][IDX][y]=dw[y];
IDX++;
if (extra==1e18) break;
//cout<<ctime<<" "<<extra<<endl;
ctime+=extra+1;
}
}
/*
rep(x,0,n){
rep(y,0,n) cout<<w2[x][y]<<" "; cout<<endl;
}
//*/
vector<ll> ans;
rep(x,0,q){
ll a=U[x],b=V[x],c=T[x];
int iter=ub(all(t[a]),c)-t[a].begin()-1;
ll res=w[a][iter][b]+(c-t[a][iter]);
rep(y,0,n) if (w[a][iter][y]<1e18){
res=min(res,w2[y][b]+s);
}
ans.pub(res-c);
}
//for (auto &it:ans) cout<<it<<" "; cout<<endl;
return ans;
}
