#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+6;
int sz=0;
bool vis[MAXN];
std::vector<std::pair<int,int> > g[MAXN];
int mpd[MAXN];// max path down
int biggest_current;
void dfs_init(int u,int par)
{
mpd[u]=0;
vis[u]=1;
vector<int>f;
for(auto xd:g[u])
{
if(xd.first==par)continue;
dfs_init(xd.first,u);
mpd[u]=max(xd.second+mpd[xd.first],mpd[u]);
f.push_back(mpd[xd.first]+xd.second);
}
biggest_current=max(biggest_current,mpd[u]);
sort(f.rbegin(),f.rend());
if(f.size()>1)biggest_current=max(biggest_current,f[0]+f[1]);
}
int dfs_find(int u,int par,int len_up)
{
int ret=max(mpd[u],len_up);
int maxd=-1,ch=-1,che=-1;
for(auto xd:g[u])
{
if(xd.first==par)continue;
if(mpd[xd.first]>maxd)
{
maxd=mpd[xd.first];
ch=xd.first;
che=xd.second;
}
}
if(ch==-1)
{
return ret;
}
len_up+=che;
for(auto xd:g[u])
{
if(xd.first==par)continue;
if(xd.first==ch)continue;
len_up=max(len_up,mpd[xd.first]+che+xd.second);
}
return min(ret,dfs_find(ch,u,len_up));
}
void solve(int u)
{
dfs_init(u,0);
sz=dfs_find(u,0,0);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(int i=0;i<M;i++)
{
A[i]++;
B[i]++;
g[A[i]].push_back({B[i],T[i]});
g[B[i]].push_back({A[i],T[i]});
}
vector<int>comps;
for(int i=1;i<=N;i++)
{
if(vis[i]==0)
{
sz=0;
solve(i);
comps.push_back(sz);
}
}
sort(comps.rbegin(),comps.rend());
int ans=biggest_current;
if(comps.size()==1)return max(ans,comps[0]);
if(comps.size()==2)return max(ans,comps[0]+comps[1]+L);
return max(ans,max(comps[0]+comps[1]+L,comps[1]+comps[2]+L+L));
}
