#include "dreaming.h"
#include <bits/stdc++.h>
#define MAXN 100005
#define INF (ll)1e9+5
using namespace std;
typedef long long ll;
vector<pair<int,ll>> adj[MAXN];//(to,weight)
ll dp_down1[MAXN],dp_down2[MAXN],dp_d[MAXN],dp_up[MAXN],ans[MAXN];
bool visited[MAXN];
ll min_len,id_min;
vector<pair<ll,int>> rep;//(weight,id)
int n;
ll res;
void dfs1(int curr,int par=-1){
visited[curr]=true;
for(auto p:adj[curr]){
int to = p.first;
ll w = p.second;
if(to==par) continue;
dfs1(to,curr);
if(dp_down1[to]+w>dp_down1[curr]){
dp_down1[curr]=dp_down1[to]+w;
dp_d[curr]=to;
}
}
for(auto p:adj[curr]){
int to = p.first;
ll w = p.second;
if(to==par||to==dp_d[curr]) continue;
if(dp_down1[to]+w>dp_down2[curr]){
dp_down2[curr]=dp_down1[to]+w;
}
}
}
void dfs2(int curr,int par=-1,int wpar=0){
if(par!=-1){
if(dp_d[par]!=curr) dp_up[curr]=max(dp_up[par],dp_down1[par])+wpar;
else dp_up[curr]=max(dp_up[par],dp_down2[par])+wpar;
}
ans[curr]=max(dp_up[curr],dp_down1[curr]);
if(ans[curr]<min_len){
min_len=ans[curr];
id_min=curr;
}
res=max(res,ans[curr]);
for(auto p:adj[curr]){
int to = p.first;
ll w = p.second;
if(to==par) continue;
dfs2(to,curr,w);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(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(int i=0;i<N;i++){
if(!visited[i]){
min_len=INF;
dfs1(i);
dfs2(i);
rep.push_back({min_len,id_min});
}
}
sort(rep.begin(),rep.end());
int rsize=rep.size();
if(rsize==1){
return res;
}else if(rsize==2){
return max(rep[rsize-1].first+rep[rsize-2].first+L,res);
}else{
return max({rep[rsize-1].first+rep[rsize-2].first+L,rep[rsize-2].first+rep[rsize-3].first+2*L,res});
}
}
