#include "escape_route.h"
#include <bits/stdc++.h>
#define pb push_back
#define endl ("\n")
#define all(aa) aa.begin(), aa.end()
typedef long long ll;
using namespace std;
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) {
const ll inf = 1e18;
vector<vector<array<ll, 3>>> g(n);
for(int i = 0; i < m; i++){
g[A[i]].pb({B[i], L[i], C[i]});
g[B[i]].pb({A[i], L[i], C[i]});
}
vector<vector<ll>> mes(n, vector<ll>(n, inf));
for(int u = 0; u < n; u++){
priority_queue<array<ll, 2>, vector<array<ll, 2>>, greater<array<ll, 2>>> pq;
pq.push({0, u});
vector<int> vis(n);
while(!pq.empty()){
auto [d, v] = pq.top(); pq.pop();
if(vis[v]) continue;
vis[v] = 1;
mes[u][v] = d;
for(auto [go, len, tim] : g[v]){
if(!vis[go] && d + len <= tim){
pq.push({d + len, go});
}
}
}
}
vector<vector<int>> gidible(n);
for(int u = 0; u < n; u++){
for(int v = 0; v < n; v++){
if(mes[u][v] != inf)
gidible[u].pb(v);
}
}
vector<ll> ans(q, inf);
for(int qq = 0; qq < q; qq++){
int uu = U[qq], vv = V[qq], tt = T[qq];
set<int> s;
priority_queue<array<ll, 2>, vector<array<ll, 2>>, greater<array<ll, 2>>> pq;
pq.push({tt, uu});
vector<int> vis(n);
while(!pq.empty()){
auto [d, v] = pq.top(); pq.pop();
if(vis[v]) continue;
vis[v] = 1;
if(v == vv){
ans[qq] = d - tt;
}
s.insert(v);
for(auto [go, len, tim] : g[v]){
if(!vis[go] && d + len <= tim){
pq.push({d + len, go});
}
}
}
ll days = 1;
while(ans[qq] == inf){
vector<int> add;
for(int u : s){
if(mes[u][vv] != inf){
ans[qq] = min(ans[qq], mes[u][vv] + days * S - tt);
}
for(int go : gidible[u]){
if(!vis[go]){
vis[go] = 1;
add.pb(go);
}
}
}
s.clear();
for(int u : add) s.insert(u);
add.clear();
days++;
}
}
return ans;
}
// int main(){
// int n, m, q;
// ll s;
// cin >> n >> m >> s >> q;
// vector<int> a(m), b(m);
// vector<ll> l(m), c(m);
// for(int i = 0; i < m; i++){
// cin >> a[i] >> b[i] >> l[i] >> c[i];
// }
// vector<int> u(q), v(q);
// vector<ll> t(q);
// for(int i = 0; i < q; i++){
// cin >> u[i] >> v[i] >> t[i];
// }
// auto ar = calculate_necessary_time(n, m, s, q, a, b, l, c, u, v, t);
// for(auto x : ar){
// cout << x << endl;
// }
// }
