#include "dreaming.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int nmax=100005;
vector< pair<int,int> > v[nmax];
vector<int> centr;
int d[nmax],viz[nmax],rep[nmax],dist[nmax];
int far,root,n,nr,i,x,mx,mn,ans,maxdiam;
void dfs(int x)
{
int nod=0;
viz[x]=1;rep[++nr]=x;
for(int i=0;i<v[x].size();i++)
{
nod=v[x][i].first;
if(!viz[nod])
{
d[nod]=d[x]+v[x][i].second;
dfs(nod);
}
}
}
void get_diam()
{
far=root;nr=0;
dfs(root);
for(i=1;i<=nr;i++)
{
x=rep[i];
if(d[x]>d[far])
far=x;
viz[x]=0;
}
nr=0;d[far]=0;
dfs(far);
for(i=1;i<=nr;i++)
{
x=rep[i];
if(d[x]>d[far])
far=x;
dist[x]=max(dist[x],d[x]);
if(d[x]>maxdiam)
maxdiam=d[x];
viz[x]=0;
}
d[far]=0;nr=0;
dfs(far);
for(i=1;i<=nr;i++)
{
x=rep[i];
dist[x]=max(dist[x],d[x]);
}
mn=(1<<30);
for(i=1;i<=nr;i++)
{
x=rep[i];
if(dist[x]<mn)
mn=dist[x];
}
centr.push_back(mn);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n=N;
for(i=0;i<M;i++)
{
v[A[i]].push_back({B[i],T[i]});
v[B[i]].push_back({A[i],T[i]});
}
for(root=0;root<n;root++)
if(!viz[root])
get_diam();
sort(centr.begin(),centr.end());
if(centr.size()==1)
{
ans=maxdiam;
}
if(centr.size()==2)
{
ans=centr[0]+centr[1]+L;
}
if(centr.size()>2)
{
x=centr.size();
ans=max(centr[x-1]+L+centr[x-2],centr[x-2]+2*L+centr[x-3]);
}
return max(ans,maxdiam);
}
