#include "dreaming.h"
#include <vector>
#include <stdio.h>
using namespace std;
vector < pair < long long , long long > > Next[100005];
bool have[100005]={0};
long long a=0,b=0,c=0,t=0,big=0,bb=0,where;
void F(long long here,long long con)
{
if(con>=big)
{
big=con;
where=here;
}
have[here]=1;
for(auto i:Next[here]) if(!have[i.first]) F(i.first,con+i.second);
}
void F2(long long here,long long Father,long long con)
{
t=min(t,max(con,big-con));
for(auto i:Next[here]) if(i.first!=Father) F2(i.first,here,con+i.second);
}
void F3(long long here,long long Father,long long con)
{
big=max(big,con);
for(auto i:Next[here]) if(i.first!=Father) F3(i.first,here,con+i.second);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
long long i,how=0;
for(i=0;i<M;i++)
{
Next[A[i]].push_back(make_pair((long long)B[i],(long long)T[i]));
Next[B[i]].push_back(make_pair((long long)A[i],(long long)T[i]));
}
for(i=0;i<N;i++)
{
if(!have[i])
{
how++;
big=0;
where=0;
F(i,0);
F3(where,-1,0);
bb=max(bb,big);
t=1e9;
F2(where,-1,0);
if(t>=a)
{
c=b;
b=a;
a=t;
}
else if(t>=b)
{
c=b;
b=t;
}
else if(t>=c) c=t;
}
}
//printf("%d %d %d %d %d\n",how,bb,a,b,c);
if(how>=2) bb=max(bb,a+b+L);
if(how>=3) bb=max(bb,b+c+2*L);
return (int) bb;
}
