#include "dreaming.h"
#include <vector>
#include <algorithm>
#include <functional>
#include <cstdio>
const int INF=1e9+7;
std::vector<std::pair<int,int> > adj[100005];
int vis[100005];
std::vector<std::pair<int,int> > down[100005];
int solo=0;
void dfs1(int node){
vis[node]=1;
down[node].push_back({0,node});
for(auto e:adj[node]){
int child=e.first;
if(vis[child]==1) continue;
dfs1(child);
down[node].push_back({down[child][0].first+e.second,child});
}
std::sort(down[node].begin(),down[node].end(),std::greater<std::pair<int,int> >());
if(down[node].size()>=2){
solo=std::max(solo,down[node][0].first+down[node][1].first);
}
}
void dfs2(int node,int up,int& far){
vis[node]=2;
far=std::min(far,std::max(up,down[node][0].first));
solo=std::max(solo,up+down[node][0].first);
for(auto e:adj[node]){
int child=e.first;
if(vis[child]==2) continue;
dfs2(child,std::max(up,down[node][child==down[node][0].second].first)+e.second,far);
}
}
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]});
}
std::vector<int> trees;
for(int i=0;i<N;i++){
if(!vis[i]){
int far=INF;
dfs1(i);
dfs2(i,0,far);
trees.push_back(far);
//fprintf(stderr,"TREE: %d\n",far);
}
}
std::sort(trees.begin(),trees.end(),std::greater<int>());
int ans=solo;
if(trees.size()>=2){
ans=std::max(ans,trees[0]+trees[1]+L);
}
if(trees.size()>=3){
ans=std::max(ans,trees[1]+trees[2]+L*2);
}
return ans;
}
