#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std ;
const int N = 1e5 + 7 ;
int mn ;
int vis[N] ;
int mxx[N] ;
int anss[N] ;
vector<pair<int , int > > adj[N];
int node , dst ;
int ansi , ans2;
int solve1(int x, int p){
int ret = 0 ;
for(auto u : adj[x]){
if(u.first==p)continue ;
int dfx = solve1(u.first , x) + u.second ;
ret = max(ret , dfx) ;
}
anss[x] = ret ;
return mxx[x] = ret ;
}
void dfs(int x , int p , int h){
for(auto u : adj[x]){
if(u.first==p)continue ;
dfs(u.first , x , h + u.second) ;
}
if( h > dst){
node = x ;
dst = h ;
}
ans2 = max(ans2 , h) ;
}
int dfs1(int x, int p , int dp = 0 ){
vis[x] ++ ;
anss[x] = max(anss[x] , dp ) ;
ansi = min(ansi , anss[x]) ;
multiset<int> dps ;
for(auto u : adj[x]){
if(u.first == p)continue ;
dps.insert(mxx[u.first] + u.second) ;
}
for(auto u : adj[x]){
if(u.first==p)continue ;
int subdp = 0 ;
dps.erase(dps.find(mxx[u.first] + u.second)) ;
if(dps.size()){
auto it = dps.end() ;
it-- ;
subdp = *it ;
}
dfs1(u.first , x , max(dp , subdp) + u.second) ;
dps.insert(mxx[u.first] + u.second) ;
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(int i =0 ; i< M ;i++){
adj[A[i] +1 ].push_back({B[i]+1 , T[i]}) ;
adj[B[i]+1].push_back({A[i]+1 , T[i]}) ;
}
vector<int> v;
multiset<int> mul ;
for(int i = 1; i <=N ; i++){
if(vis[i])continue ;
ansi = 2e9 ;
dfs(i , i , 0) ; dst = 0 ;
dfs(node , node , 0) ;
solve1(i , i ) ;
dfs1(i , i) ;
v.push_back(ansi) ;
mul.insert(ansi) ;
}
if(v.size() == 1)return ans2 ;
else if(v.size() ==2 )return max(v[0] + v[1] + L , ans2) ;
int s = v.size() ;
int ans = 2e9 ;
for(auto u : v){
mul.erase(mul.find(u)) ;
int mx1 = -1 , mx2 = -1 ;
auto e = mul.end() ;
e-- ; mx1 = *e ;
e-- ; mx2 = *e ;
int now = max(u + mx1 + L , mx1 + mx2 + L + L ) ;
ans = min(ans , now ) ;
mul.insert(u) ;
}
return max(ans , ans2) ;
}
