#include "escape_route.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
std::vector<long long> calculate_necessary_time(
int32_t N, int32_t M, long long S, int32_t Q, std::vector<int32_t> A, std::vector<int32_t> B,
std::vector<long long> L, std::vector<long long> C, std::vector<int32_t> U,
std::vector<int32_t> V, std::vector<long long> T) {
vector<vector<tuple<int,int,int>>> adj(N);
vector<vector<tuple<int,int,int,int>>> sadj(N);
map<pair<int,int>,int> lookup;
for(int i=0;i<M;i++){
lookup[{A[i],B[i]}]=i;
lookup[{B[i],A[i]}]=i;
adj[A[i]].emplace_back(B[i],L[i],C[i]);
adj[B[i]].emplace_back(A[i],L[i],C[i]);
sadj[A[i]].emplace_back(C[i]-L[i],B[i],L[i],i);
sadj[B[i]].emplace_back(C[i]-L[i],A[i],L[i],i+M);
}
for(int i=0;i<N;i++)sort(sadj[i].rbegin(),sadj[i].rend());
vector<vector<int>> distances(N,vector<int>(N));
for(int i=0;i<N;i++){
priority_queue<pair<int,int>> q;
q.emplace(0,i);
vector<int> visited(N,1e18);
vector<bool> vis(N);
visited[i] = 0;
while(!q.empty()){
auto [dist,idx] = q.top();q.pop();dist=-dist;
if(vis[idx])continue;
vis[idx]=true;
for(auto[v,l,c]:adj[idx])if(!vis[v]){
int nxttime = 0;
int currtime = dist%S;
if(currtime<=c-l)nxttime=dist+l;
else {
nxttime = (dist/S)*S+l+S;
}
if(nxttime<visited[v]){
visited[v]=nxttime;
q.emplace(-nxttime,v);
}
}
}
distances[i]=visited;
}
vector<int> ans(Q);
vector<vector<tuple<int,int,int>>> queries(N);
for(int i=0;i<Q;i++)queries[U[i]].emplace_back(T[i],i,V[i]);
for(int i=0;i<N;i++)sort(queries[i].rbegin(),queries[i].rend());
vector<vector<int>> distancesviaedge(2*M);
for(int i=0;i<M;i++){
// Say we depart from A[i] for x=i and B[i] for x=i+m at C[i]-L[i]
vector<bool> vis(N);
vector<int> disti(N,INF);
priority_queue<pair<int,int>> q;
q.emplace(-(C[i]-L[i]),A[i]);
while(!q.empty()){
auto [dist,idx] = q.top();q.pop();dist=-dist;
if(vis[idx])continue;
vis[idx]=true;
disti[idx] = dist-(C[i]-L[i]);
for(auto[v,l,c]:adj[idx])if(dist<=c-l and !vis[v])q.emplace(-dist-l,v);
}
distancesviaedge[i]=disti;
}
for(int i=0;i<M;i++){
// Say we depart from A[i] for x=i and B[i] for x=i+m at C[i]-L[i]
vector<bool> vis(N);
vector<int> disti(N,INF);
priority_queue<pair<int,int>> q;
q.emplace(-(C[i]-L[i]),B[i]);
while(!q.empty()){
auto [dist,idx] = q.top();q.pop();dist=-dist;
if(vis[idx])continue;
vis[idx]=true;
disti[idx] = dist-(C[i]-L[i]);
for(auto[v,l,c]:adj[idx])if(dist<=c-l and !vis[v])q.emplace(-dist-l,v);
}
distancesviaedge[i+M]=disti;
}
for(int i=0;i<N;i++){
set<pair<int,int>> edges;
vector<int> dist(N,INF);
vector<int> addedidx(N);
auto update_node = [&](int x,int newd){
if(newd>=dist[x])return;
if(dist[x]>=INF){
// First time adding
edges.insert(make_pair(get<0>(sadj[x][0])-newd,get<3>(sadj[x][0])));
} else if(addedidx[x]!=sadj[x].size()) {
edges.erase(make_pair(get<0>(sadj[x][addedidx[x]])-dist[x],get<3>(sadj[x][addedidx[x]])));
edges.insert(make_pair(get<0>(sadj[x][addedidx[x]])-newd,get<3>(sadj[x][addedidx[x]])));
}
dist[x]=newd;
};
auto update_edge = [&](int e){
int v = -1;
if(e>=M)v=B[e-M];
else v=A[e];
edges.erase(make_pair(get<0>(sadj[v][addedidx[v]])-dist[v],get<3>(sadj[v][addedidx[v]])));
addedidx[v]++;
if(addedidx[v]!=sadj[v].size())edges.insert(make_pair(get<0>(sadj[v][addedidx[v]])-dist[v],get<3>(sadj[v][addedidx[v]])));
for(int x=0;x<N;x++)update_node(x,dist[v]+distancesviaedge[e][x]);
};
update_node(i,0);
for(auto[tim,idx,dest]:queries[i]){
while(!edges.empty() and (--edges.end())->first>=tim)update_edge((--edges.end())->second);
ans[idx] = dist[dest];
for(int j=0;j<N;j++){
if(dist[j]>=INF)continue;
ans[idx] = min(ans[idx],distances[j][dest]+S-tim);
}
}
}
return ans;
}
