#include<bits/stdc++.h>
#include "escape_route.h"
using namespace std;
const long long N = 41;
const long long inf = 1e16;
long long n, m, s, q;
long long dp[N][N];
vector <array <long long, 3>> g[N];
long long dist[N];
long long last[N];
void solve(long long st){
dp[st][st] = 0;
for(long long i = 0;i < n;i++){
dist[i] = inf;
}
dist[st] = 0;
priority_queue <pair <long long, long long>> pq;
pq.push({0, st});
while(!pq.empty()){
auto [tempo, v] = pq.top();
pq.pop();
tempo *= -1;
if(tempo != dist[v]) continue;
for(auto [x, l, c] : g[v]){
if(dist[v]+l > c) continue;
if(dist[v]+l < dist[x]){
dist[x] = dist[v]+l;
dp[st][x] = dist[x];
pq.push({-dist[x], x});
}
}
}
return;
}
pair <long long, long long> dist2[N];
vector <long long> answer;
void solve2(long long u, long long v, long long t){
set <long long> vertices;
for(long long i = 0;i < n;i++){
dist[i] = inf;
}
dist[u] = t;
priority_queue <pair <long long, long long>> pq;
pq.push({-t, u});
while(!pq.empty()){
auto [tempo, v] = pq.top();
pq.pop();
tempo *= -1;
if(tempo != dist[v]) continue;
vertices.insert(v);
for(auto [x, l, c] : g[v]){
if(dist[v]+l > c) continue;
if(dist[v]+l < dist[x]){
dist[x] = dist[v]+l;
pq.push({-dist[x], x});
}
}
}
for(long long i = 0;i < n;i++){
dist2[i] = {90, inf};
}
for(auto i : vertices){
dist2[i] = {0, dist[i]};
pq.push({-s*dist2[i].first-dist2[i].second, i});
}
while(!pq.empty()){
auto [d, v] = pq.top();
pq.pop();
d *= -1;
//cout << d << ' ' << v << '\n';
if(d != dist2[v].first*s+dist2[v].second) continue;
for(long long i = 0;i < n;i++){
if(dp[v][i] > -1){
if((dist2[v].first+1)*s+dp[v][i] < dist2[i].first*s+dist2[i].second){
dist2[i] = make_pair(dist2[v].first+1, dp[v][i]);
pq.push({-s*dist2[i].first-dist2[i].second, i});
}
}
}
}
answer.push_back(dist2[v].first*s+dist2[v].second-t);
}
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) {
memset(dp, -1, sizeof dp);
n = N;
m = M;
s = S;
q = Q;
for(long long i = 0;i < m;i++){
long long a, b, l, c;
a = A[i];
b = B[i];
l = L[i];
c = C[i];
g[a].push_back({b, l, c});
g[b].push_back({a, l, c});
}
for(long long i = 0;i < n;i++){
solve(i);
}
for(int i = 0;i < q;i++){
long long u, v, t;
u = U[i];
v = V[i];
t = T[i];
solve2(u, v, t);
}
return answer;
}
