#include<dreaming.h>
#include<vector>
#include<algorithm>
using namespace std;
vector<pair<int,int> > V[100005];
int DistMax[100005],Dist[100005],R[100005],Viz[100005];
int dfs(int nod, int cc)
{
Viz[nod]=cc;
int mx1=0,mx2=0;
int rez=0;
for(auto other:V[nod])
{
if(Viz[other.first])
continue;
rez=max(rez,dfs(other.first,cc));
int val=DistMax[other.first]+other.second;
if(val>=mx1)
{
mx2=mx1;
mx1=val;
}
else if(val>mx2)
mx2=val;
}
DistMax[nod]=mx1;
rez=max(rez,mx1+mx2);
return rez;
}
int distmin(int nod, int p, int dist)
{
int rez=max(dist,DistMax[nod]);
int mx1=0,mx2=0;
for(auto other:V[nod])
{
if(other.first==p)
continue;
int val=DistMax[other.first]+other.second;
if(val>=mx1)
{
mx2=mx1;
mx1=val;
}
else if(val>mx2)
mx2=val;
}
for(auto other:V[nod])
{
if(other.first==p)
continue;
int val=DistMax[other.first]+other.second;
if(val!=mx1)
rez=min(rez,distmin(other.first,nod,dist+other.second+mx1));
else
rez=min(rez,distmin(other.first,nod,dist+other.second+mx2));
}
return rez;
}
int travelTime(int n, int M, int L, int A[], int B[], int T[])
{
for(int i=0; i<M; i++)
{
V[A[i]+1].push_back({B[i]+1,T[i]});
V[B[i]+1].push_back({A[i]+1,T[i]});
}
int nrc=0;
int rez=0;
for(int i=1; i<=n; i++)
{
if(!Viz[i])
{
nrc++;
rez=max(rez,dfs(i,nrc));
R[nrc]=i;
}
}
for(int i=1; i<=nrc; i++)
Dist[i]=distmin(R[i],0,0);
sort(Dist+1,Dist+nrc+1);
if(nrc>=2)
rez=max(rez,Dist[nrc]+Dist[nrc-1]+L);
if(nrc>=3)
rez=max(rez,Dist[nrc-1]+Dist[nrc-2]+2*L);
return rez;
}
