#include "escape_route.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<tuple<int,ll,ll>> adj[42];
ll S;
ll tim[42];
void dijkstra(int s, ll t) {
memset(tim,69,sizeof(tim));
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
tim[s] = t;
pq.push({t, s});
while(pq.size()) {
auto [d, x] = pq.top();
pq.pop();
if(d != tim[x])
continue;
for(auto [y, l, c]: adj[x]) {
ll nwT = tim[x];
if((nwT % S) <= c - l)
nwT += l;
else
nwT = (nwT + S - 1) / S * S + l;
if(nwT < tim[y]) {
tim[y] = nwT;
pq.push({nwT,y});
}
}
}
}
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) {
::S = S;
for(int i=0;i<M;i++) {
adj[A[i]].push_back({B[i],L[i],C[i]});
adj[B[i]].push_back({A[i],L[i],C[i]});
}
vector<ll> ans;
for(int i=0;i<Q;i++) {
dijkstra(U[i], T[i]);
ans.push_back(tim[V[i]] - T[i]);
}
return ans;
}
