#include <bits/stdc++.h>
#include "dreaming.h"
int nr,t[100010],v[100010],pd[100010],n,m,l,ans;
bool viz[100010];
std::vector<std::vector<std::pair<int,int>>>a;
inline int tata(int nod)
{
if(t[nod]==nod)
return nod;
return t[nod]=tata(t[nod]);
}
inline void parcurge1(int nod,int &nod2,int &vnod2)
{
viz[nod]=true;
if(pd[nod]>vnod2)
{
vnod2=pd[nod];
nod2=nod;
}
for(auto x:a[nod])
{
if(viz[x.first]==false)
{
pd[x.first]=pd[nod]+x.second;
parcurge1(x.first,nod2,vnod2);
pd[x.first]=0;
}
}
}
inline void parcurge2(int nod,int &vnod)
{
viz[nod]=false;
if(pd[nod]>vnod)
vnod=pd[nod];
for(auto x:a[nod])
{
if(viz[x.first]==true)
{
pd[x.first]=pd[nod]+x.second;
parcurge2(x.first,vnod);
pd[x.first]=0;
}
}
}
inline int diametru(int nod)
{
int nod2=nod,vnod2=0;
parcurge1(nod,nod2,vnod2);
vnod2=0;
parcurge2(nod2,vnod2);
return vnod2;
}
inline void initpd(int nod)
{
viz[nod]=true;
for(auto x:a[nod])
{
if(viz[x.first]==false)
{
initpd(x.first);
pd[nod]=std::max(pd[nod],pd[x.first]+x.second);
}
}
}
inline int greutate(int nod)
{
int ans=1000000000,rad=nod,rado=nod;
do
{
int ansa=0;
nod=rad;
for(auto x:a[nod])
{
if(x.second+pd[x.first]>ansa)
{
ansa=x.second+pd[x.first];
rad=x.first;
}
}
if(ansa<ans)
{
ans=ansa;
rado=nod;
}
pd[nod]=0;
for(auto x:a[nod])
{
if(x.first!=rad)
{
if(x.second+pd[x.first]>pd[nod])
pd[nod]=x.second+pd[x.first];
}
}
}while(rado!=rad);
return ans;
}
inline int construieste(int nod)
{
int dim=diametru(nod);
ans=std::max(ans,dim);
if(dim==0)
return 0;
initpd(nod);
return greutate(nod);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
n=N;
m=M;
l=L;
a.resize(n+5);
ans=0;
for(int i=0;i<n;++i)
t[i]=i;
for(int i=0;i<m;++i)
{
a[A[i]].push_back({B[i],T[i]});
a[B[i]].push_back({A[i],T[i]});
t[t[A[i]]]=tata(B[i]);
}
for(int i=0;i<n;++i)
if(viz[i]==false)
v[++nr]=construieste(i);
std::sort(v+1,v+nr+1);
if(nr>=2)
ans=std::max(ans,L+v[nr]+v[nr-1]);
if(nr>=3)
ans=std::max(ans,2*L+v[nr-2]+v[nr-1]);
return ans;
}
