#include "escape_route.h"
#include <bits/stdc++.h>
#define int ll
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<ll, ll>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif
const int iinf = 1e9+10;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9+7 ;
void GG(){cout<<"0\n"; exit(0);}
//const int maxn = 1e5+5;
namespace {
const int N = 91;
bool E[N][N]; // can a reach b, given a full day?
ll L[N][N], C[N][N];
int S;
vector<ll> stime[N]; // stime i means the following distance info is for times [i, next)
vector<vector<ll> > dst[N];
int n;
int from[N];
bool done[N];
int daydst[N][N];
ll totdst[N][N];
}
ll dij(int v, ll T) {
// returns the next closest edge to being unpassable
bug(v, T);
memset(from, -1, sizeof from);
memset(done, 0, sizeof done);
vector<ll> D(n,inf);
D[v] = 0;
ll re = inf;
REP(round, n) {
int at = -1, w = inf;
REP(i,n) {
if (!done[i] && D[i] < w) {
at = i; w = D[i];
}
}
if (at == -1) break;
done[at] = 1;
if (from[at] != -1) MN(re, C[at][from[at]] - D[at]);
REP(j,n) {
if (L[at][j] && !done[j] && C[at][j] - D[at] - L[at][j] >= T && D[j] > D[at] + L[at][j]) {
// bug(at, j);
if (v == 0) {
bug(j,at,L[at][j], D[at]);
}
D[j] = D[at] + L[at][j];
from[j] = at;
}
}
}
assert(re >= 0);
stime[v].pb(T);
dst[v].pb(D);
if (T == 0) {
REP(j,n) {
E[v][j] = D[j] < inf;
bug(v,j,E[v][j]);
}
}
return re;
}
void bfs(int st) {
int *D = daydst[st];
memset(daydst[st], 0x3f, sizeof daydst[st]);
D[st] = 0;
queue<int> q; q.push(st);
while (!q.empty()) {
int v = q.front(); q.pop();
REP(j,n) {
if (E[v][j] && D[j] > D[v] + 1) {
D[j] = D[v] + 1;
q.push(j);
}
}
}
}
std::vector<long long> calculate_necessary_time(
signed en, signed M, long long eS, signed Q, std::vector<signed> eA, std::vector<signed> eB,
std::vector<long long> eL, std::vector<long long> eC, std::vector<signed> U,
std::vector<signed> V, std::vector<long long> eT) {
S = eS;
n = en;
REP(i, M) {
int a = eA[i], b = eB[i];
L[a][b] = L[b][a] = eL[i];
C[a][b] = C[b][a] = eC[i];
}
REP(i,n) {
ll now = -1;
while (now < inf) {
now = dij(i, now+1);
}
}
memset(totdst, 0x3f, sizeof totdst);
REP(i,n) {
bfs(i);
REP(j,n) {
if (daydst[i][j] < inf) {
REP(k,n) {
MN(totdst[i][k], daydst[i][j] * S + dst[j][0][k]);
}
}
}
}
bug(totdst[0][1], totdst[0][0]);
bug(totdst[0][2], totdst[0][3]);
bug(dst[0][0][2]);
bug(dst[0][0][3]);
vector<ll> re;
REP(i,Q) {
bug(i);
int u = U[i], v = V[i];
ll T = eT[i];
int ver = upper_bound(ALL(stime[u]), T) - stime[u].begin() - 1;
if (dst[u][ver][v] < inf) {
re.pb(dst[u][ver][v]);
}else{
ll ans = inf;
REP(j,n) {
if (dst[u][ver][j] < inf) {
bug(j, totdst[j][v]);
MN(ans, S-T + totdst[j][v]);
}
}
re.pb(ans);
}
}
return re;
}
//#ifdef BALBIT
//signed main(){
//
//}
//#endif // BALBIT
