#include<bits/stdc++.h>
#include "escape_route.h"
using namespace std;
#define ll long long
const ll INF=1e18;
ll dist_0[92][92]; priority_queue<pair<ll,ll> >pq; bool vis[92];
struct dat{
ll graph_id,x,y,l,timing;
bool operator<(const dat& da)const{
if(timing!=da.timing)return timing<da.timing;
return graph_id<da.graph_id;
}
bool operator>(const dat& da)const{
if(timing!=da.timing)return timing>da.timing;
return graph_id>da.graph_id;
}
bool operator==(const dat& da)const{
if(timing!=da.timing)return 0;
if(graph_id!=da.graph_id)return 0;
return 1;
}
};
struct edge{
ll v,l,c;
bool operator<(const edge& edg)const{
return ((c-l)<(edg.c-edg.l));
}
};
vector<edge>adj[91];
priority_queue<dat> q;
struct Graph{
vector<ll>dist[8101];
vector<ll>points;
vector<edge>adj[91];
vector<ll>optimals;
ll n,gid; ll ass=1;
void init(ll _n, ll _gid){
n=_n; gid=_gid;
vector<ll>d;
for(int i=0;i<=n;i++)d.push_back(INF);
d[gid]=0; dist[0]=d; points.push_back(INF);
optimals=d;
}
void add_edge(ll u, ll v, ll l, ll c){
adj[u].push_back({v,l,c}); adj[v].push_back({u,l,c});
}
void compile(){
for(int i=1;i<=90;i++){
sort(adj[i].begin(),adj[i].end());
}
auto [v,l,c]=adj[gid][adj[gid].size()-1];
q.push({gid,gid,v,l,c-l});
}
ll search(ll x){
ll l=0,r=points.size()-1;
while(l<r){
ll mid=(l+r+1)>>1;
if(points[mid]>=x)l=mid;
else r=mid-1;
}
return l;
}
bool upd(ll x, ll y, ll w){
adj[x].pop_back();
if(optimals[x]+w<optimals[y]){
optimals[y]=optimals[x]+w; return 1;
}
return 0;
}
ll exhaust_graph(vector<ll>& distances, ll starting_at, ll timer){
for(int i=1;i<=n;i++){
if(distances[i]+optimals[starting_at]<optimals[i]){
optimals[i]=optimals[starting_at]+distances[i];
}
}
dist[ass]=optimals; ass++; points.push_back(min(timer,points[ass-2]));
return points[points.size()-1];
}
void add(){
ll maxi=-2*INF; edge req; ll from;
for(int i=1;i<=n;i++){
if(adj[i].size()==0)continue;
auto [v,l,c]=adj[i][adj[i].size()-1];
if(c-l-optimals[i]>maxi){
from=i;
maxi=c-l-optimals[i]; req=adj[i][adj[i].size()-1];
}
}
if(maxi!=-2*INF){
q.push({gid,from,req.v,req.l,maxi});
}
}
// pinpoint c-l-dist
}g[91];
void Dijk(ll x, ll S){
pq.push({0,x});
dist_0[x][x]=0;
while(!pq.empty()){
ll cur=pq.top().second; pq.pop();
if(vis[cur])continue;
vis[cur]=1;
for(auto& [v,l,c]: adj[cur]){
ll req=dist_0[x][cur];
ll rem=req%S;
if(rem<=c-l){
if(req+l<dist_0[x][v]){
dist_0[x][v]=req+l; pq.push({-dist_0[x][v],v});
}
}
else{
ll new_dist=dist_0[x][cur]/S+1; new_dist*=S;
if(new_dist+l<dist_0[x][v]){
dist_0[x][v]=new_dist+l; pq.push({-dist_0[x][v],v});
}
}
}
}
}
vector<ll> calculate_necessary_time(int N, int M, long long S, int Q,
vector<int> A, vector<int> B, vector<ll> L, vector<ll> C,
vector<int> U, vector<int> V, vector<long long> T) {
for(int i=0;i<M;i++){
A[i]++; B[i]++;
adj[A[i]].push_back({B[i],L[i],C[i]}); adj[B[i]].push_back({A[i],L[i],C[i]});
}
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
dist_0[i][j]=INF;
}
}
for(int i=1;i<=N;i++){
Dijk(i,S); for(int j=1;j<=N;j++)vis[j]=0;
}
for(int i=0;i<Q;i++)U[i]++,V[i]++;
for(int i=1;i<=N;i++){
g[i].init(N,i);
}
for(int i=1;i<=N;i++){
for(int j=0;j<M;j++){
g[i].add_edge(A[j],B[j],L[j],C[j]);
}
}
for(int i=N;i>=1;i--)g[i].compile();
// dat thing={4,4,2,5,9};
// dat thing2={3,3,1,2,6};
// cout<<q.size()<<'\n';
// while(!q.empty()){
// auto [graph_id,x,y,l,timing]=q.top(); q.pop();
// cout<<graph_id<<' '<<x<<" "<<y<<" "<<l<<" "<<timing<<endl;
// }
while(!q.empty()){
auto [graph_id,x,y,l,timing]=q.top(); q.pop();
if(timing<0)break;
bool success=g[graph_id].upd(x,y,l);
ll val=-1;
if(success){
ll req=g[graph_id].optimals[y];
ll id=g[y].search(timing+req);
val=g[graph_id].exhaust_graph(g[y].dist[id],y,timing);
}
g[graph_id].add();
}
// vector<ll>ans; return ans;
vector<ll>ans;
for(int i=0;i<Q;i++){
ll u=U[i],v=V[i],t=T[i];
ll id=g[u].search(t);
if(g[u].dist[id][v]!=INF){
ans.push_back(g[u].dist[id][v]);
}
else{
ll bst=2*INF;
for(int j=1;j<=N;j++){
if(g[u].dist[id][j]!=INF){
bst=min(bst,dist_0[j][v]+S-t);
}
}
ans.push_back(bst);
}
}
return ans;
}
// int main(){
// ios::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
// ll n,m,s,q;
// cin>>n>>m>>s>>q;
// vector<ll>L,C,T;
// vector<int>A,B,U,V;
// for(int i=0;i<m;i++){
// ll a,b,l,c;
// cin>>a>>b>>l>>c;
// A.push_back(a);
// B.push_back(b);
// L.push_back(l);
// C.push_back(c);
// }
// for(int i=0;i<q;i++){
// ll u,v,t;
// cin>>u>>v>>t;
// U.push_back(u);
// V.push_back(v);
// T.push_back(t);
// }
// vector<ll>ans=calculate_necessary_time(n,m,s,q,A,B,L,C,U,V,T);
// for(auto& u: ans)cout<<u<<'\n';
// }
