#include "escape_route.h"
#include <bits/stdc++.h>
using namespace std;
namespace{
const long long int inf = 1.1e18;
} long long int d[100][5100][100];
vector<long long> calculate_necessary_time(
int N, int M, long long S, int Q, vector<int> A, vector<int> B,
vector<long long> L, vector<long long> C, vector<int> U,
vector<int> V, vector<long long> T) {
vector<int> adjlst[100];
vector<vector<long long int>> ds[100];
vector<long long int> turns[100];
vector<long long int> turns1[100];
bool used[100];
int dit[100];
pair<long long int, long long int> adjmat[100][100];
for(int i = 0; i < M; i++){
A.push_back(B[i]);
B.push_back(A[i]);
L.push_back(L[i]);
C.push_back(C[i]);
}
for(int i = 0; i < M; i++){
adjlst[A[i]].push_back(i);
adjlst[B[i]].push_back(i + M);
}
for(int i = 0; i < N; i++){
for(int j : adjlst[i]) turns[i].push_back(C[j] - L[j]);
sort(turns[i].begin(),turns[i].end(), greater<long long int>());
turns[i].resize(unique(turns[i].begin(),turns[i].end()) - turns[i].begin() );
}
for(int i = 0; i < N; i++){
for(int j = 0; j < turns[i].size(); j++){
vector<long long int> temp = {};
for(int j = 0; j < N; j++){
temp.push_back(inf);
used[j] = false;
}
ds[i].push_back(temp);
ds[i][j][i] = turns[i][j];
for(int k = 0; k < N; k++){
pair<long long int, int> ii = {inf,-1};
for(int l = 0; l < N; l++) if(!used[l]) ii = min(ii,{ds[i][j][l],l });
if(ii.first == inf) break;
used[ii.second] = true;
int it = ii.second;
for(int l : adjlst[it]){
if(ii.first + L[l] <= C[l]) ds[i][j][B[l]] = min(ds[i][j][B[l]], ii.first + L[l]);
}
}
}
}
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
adjmat[i][j] = {inf,inf};
}
}
for(int i = 0; i < N; i++){
long long int incre = turns[i][0];
long long int diff = inf;
//it 1
turns1[i].push_back(incre);
for(int j = 0; j < N; j++){
dit[j] = 0;
d[i][0][j] = ds[i][0][j];
}
for(int j = 0; j < N; j++){
if(d[i][0][j] == inf) continue;
while(dit[j] != turns[j].size() && turns[j][dit[j]] >= d[i][0][j]){
dit[j]++;
}
if(dit[j] == turns[j].size()) continue;
diff = min(diff,d[i][0][j] - turns[j][dit[j]] );
}
incre = incre - diff;
//it
for(int l = 1; l < M * 2 + 5; l++){
if(incre < 0) break;
turns1[i].push_back(incre);
for(int j = 0; j < N; j++) d[i][l][j] = inf;
for(int j = 0; j < N; j++){
if(dit[j] == turns[j].size()) continue;
if(d[i][l - 1][j] - turns[j][dit[j]] != diff) continue;
for(int k = 0; k < N; k++){
if(d[i][l - 1][k] == inf && ds[j][dit[j]][k] == inf) d[i][l][k] = min(d[i][l][k], inf);
else d[i][l][k] = min(d[i][l][k], min(ds[j][dit[j]][k], d[i][l - 1][k] - diff));
}
dit[j]++;
}
diff = inf;
for(int j = 0; j < N; j++){
if(d[i][l][j] == inf) continue;
while(dit[j] != turns[j].size() && turns[j][dit[j]] >= d[i][l][j]){
dit[j]++;
}
if(dit[j] == turns[j].size()) continue;
diff = min(diff,d[i][l][j] - turns[j][dit[j]] );
}
if(incre - diff < 0) break;
incre = incre - diff;
}
if(incre < 0) incre += diff;
int it = turns1[i].size() - 1;
for(int j = 0; j < N; j++){
if(d[i][it][j] == inf) continue;
adjmat[i][j] = {1,d[i][it][j] - incre};
}
}
for(int k = 0; k < N; k++){
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
adjmat[i][j] = min(adjmat[i][j],{adjmat[i][k].first + adjmat[k][j].first, adjmat[k][j].second });
}
}
}
/*printf("\n");
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
printf("%lld ",adjmat[i][j].first);
}
printf("\n");
}
printf("\n");*/
vector<long long> ans;
for(int i = 0; i < Q; i++){
int u = U[i];
int v = V[i];
long long int h = T[i];
int it = upper_bound(turns1[u].begin(),turns1[u].end(),h,greater<long long>()) - turns1[u].begin() - 1;
if(it != -1 && d[u][it][v] != inf){
ans.push_back(d[u][it][v] - d[u][it][u]);
//printf("yes %lld\n",ans.back());
}
else{
if(it == -1){
ans.push_back(adjmat[u][v].first * S + adjmat[u][v].second - h);//printf("2 %lld\n",ans.back());
continue;
}
pair<long long int,long long int> ii = {inf,inf};
for(int j = 0; j < N; j++){
if(d[u][it][j] != inf) ii = min(adjmat[j][v],ii);
}
ans.push_back(ii.first * S + ii.second - h);
//printf("%lld\n",ans.back());
}
}
return ans;
}
/*
int main(){
int N;
int M;
long long int S;
int Q;
vector<int> A;
vector<int> B;
vector<long long int> L;
vector<long long int> C;
vector<int> U;
vector<int> V;
vector<long long int> T;
scanf(" %d",&N);
scanf(" %d",&M);
scanf(" %lld",&S);
scanf(" %d",&Q);
for(int i = 0; i < M; i++){
int h,h1;
long long int h2,h3;
scanf(" %d",&h);
scanf(" %d",&h1);
scanf(" %lld",&h2);
scanf(" %lld",&h3);
A.push_back(h);
B.push_back(h1);
L.push_back(h2);
C.push_back(h3);
}
for(int i = 0; i < Q; i++){
int h1,h2;
long long int h3;
scanf(" %d",&h1);
scanf(" %d",&h2);
scanf(" %lld",&h3);
U.push_back(h1);
V.push_back(h2);
T.push_back(h3);
}
printf("yes\n");
vector<long long int> ans = calculate_necessary_time(N,M,S,Q,A,B,L,C,U,V,T);
for(long long int j : ans) printf("%lld\n",j);
}*/
