#include <bits/stdc++.h>
#include "dreaming.h"
#define Big_INT long long
Big_INT maxdist1[100010];
Big_INT maxdist2[100010];
Big_INT maxdist3[100010];
std::vector<std::vector<std::pair<Big_INT,Big_INT>>> adj;
std::vector<Big_INT> currentNum;
void bfs(Big_INT start){
std::queue<std::pair<Big_INT,Big_INT>> q;
q.push({start,0});
maxdist1[start]=0;
while(!q.empty()){
Big_INT curr = q.front().first;
currentNum.push_back(curr);
Big_INT currw = q.front().second;
q.pop();
for(auto [to,w]:adj[curr]){
if(maxdist1[to]==-1){
maxdist1[to]=currw+w;
q.push({to,currw+w});
}
}
}
}
void bfs2(Big_INT start){
std::queue<std::pair<Big_INT,Big_INT>> q;
q.push({start,0});
maxdist2[start]=0;
while(!q.empty()){
Big_INT curr = q.front().first;
//currentNum.push_back(curr);
Big_INT currw = q.front().second;
q.pop();
for(auto [to,w]:adj[curr]){
if(maxdist2[to]==-1){
maxdist2[to]=currw+w;
q.push({to,currw+w});
}
}
}
}
void bfs3(Big_INT start){
std::queue<std::pair<Big_INT,Big_INT>> q;
q.push({start,0});
maxdist3[start]=0;
while(!q.empty()){
Big_INT curr = q.front().first;
//currentNum.push_back(curr);
Big_INT currw = q.front().second;
q.pop();
for(auto [to,w]:adj[curr]){
if(maxdist3[to]==-1){
maxdist3[to]=currw+w;
q.push({to,currw+w});
}
}
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
adj.resize(N);
for(Big_INT i=0;i<M;i++){
adj[A[i]].push_back({B[i],T[i]});
adj[B[i]].push_back({A[i],T[i]});
}
for(Big_INT i=0;i<N;i++){
maxdist1[i]=-1;
maxdist2[i]=-1;
maxdist3[i]=-1;
}
std::vector<Big_INT> value;
for(Big_INT i=0;i<N;i++){
if(maxdist1[i]==-1){
bfs(i);
Big_INT nodeA=i,distA=0;
for(auto vNode:currentNum){
if(maxdist1[vNode]>distA){
nodeA=vNode;
distA=maxdist1[vNode];
}
}
bfs2(nodeA);
Big_INT nodeB=nodeA,distB=0;
for(auto vNode:currentNum){
if(maxdist2[vNode]>distB){
nodeB=vNode;
distB=maxdist2[vNode];
}
}
bfs3(nodeB);
Big_INT minmax=1e18;
for(auto vNode:currentNum){
minmax=std::min(minmax,std::max(maxdist2[vNode],maxdist3[vNode]));
}
currentNum.resize(0);
value.push_back(minmax);
}
}
std::sort(value.begin(),value.end());
Big_INT max=value.back();
if(value.size()>=2){
max=std::max(max,value[value.size()-2]+L);
}
return max;
}
