#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]) ;
vector<int> dps , pre , suf;
for(auto u : adj[x]){
if(u.first == p)continue ;
dps.push_back(mxx[u.first] + u.second) ;
int mx = pre.size() ? pre.back() : 0 ;
pre.push_back(max(mx , dps.back())) ;
}
suf.resize(pre.size()) ;
if(suf.size())
suf[suf.size()-1] = dps[suf.size()-1] ;
for(int i = suf.size() -2 ; i >=0 ;i --){
suf[i] = max(dps[i] , suf[i+1]) ;
}
int i = 0 ;
for(auto u : adj[x]){
if(u.first==p)continue ;
int subdp = 0 ;
if(i) subdp = max(subdp , pre[i-1]) ;
if(i < suf.size() -1 ) subdp = max(subdp , suf[i+1]) ;
dfs1(u.first , x , max(dp , subdp) + u.second) ;
i++;
}
}
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;
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) ;
}
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 ;
sort(v.begin() , v.end()) ;
for(int i = 0 ; i < s ; i++){
int cur = v[i] + v.back() ;
if( i < s -1){
if( i == s-2){
cur = max(cur , v.back() + v[s-3] + L) ;
}
else cur = max(cur , v.back() + v[s-2] + L) ;
}
ans = min(ans , cur) ;
}
return max(ans + L , ans2) ;
}
