#include "dreaming.h"
#include <stdio.h>
#include <algorithm>
#include <vector>
#define M 100000
using namespace std;
int sta[M*2+1],chi[M*2+1],wei[M*2+1],nxt[M*2+1];
int n,m,l,d[2][M+1],v[2][M+1],itr;
vector<int> vec;
bool ch[M+1];
void addEdge(int x,int y,int w){
nxt[++m]=sta[x];
sta[x]=m;
chi[m]=y;
wei[m]=w;
}
int DFS1(int x,int p){
int i;
for(i=sta[x];i;i=nxt[i]){
if(chi[i]!=p){
int k=DFS1(chi[i],x)+wei[i];
if(d[0][x]<k){
d[1][x]=d[0][x];
v[1][x]=v[0][x];
d[0][x]=k;
v[0][x]=i;
}
else if(d[1][x]<k){
d[1][x]=k;
v[1][x]=i;
}
}
}
return d[0][x];
}
int DFS2(int x,int s,int p){
int i,ret;
if(d[0][x]<s){
d[1][x]=d[0][x];
v[1][x]=v[0][x];
d[0][x]=s;
v[0][x]=-1;
}
else if(d[1][x]<s){
d[1][x]=s;
v[1][x]=-1;
}
ret=d[0][x];
ch[x]=true;
for(i=sta[x];i;i=nxt[i]){
if(chi[i]!=p){
int k;
if(v[0][x]!=i){
k=DFS2(chi[i],d[0][x]+wei[i],x);
}
else{
k=DFS2(chi[i],d[1][x]+wei[i],x);
}
ret=min(ret,k);
}
}
itr=max(itr,d[0][x]+d[1][x]);
return ret;
}
int travelTime(int _n, int _m, int _l, int A[], int B[], int T[]) {
int i;
n=_n; l=_l;
for(i=0;i<_m;i++){
addEdge(A[i],B[i],T[i]);
addEdge(B[i],A[i],T[i]);
}
for(i=0;i<n;i++){
if(!ch[i]){
DFS1(i,-1);
vec.push_back(DFS2(i,0,-1));
}
}
int mx1=-1,mx2=-1,mx3=-1;
for(i=0;i<vec.size();i++){
if(mx3<vec[i]){mx3=vec[i];}
if(mx2<vec[i]){mx3=mx2;mx2=vec[i];}
if(mx1<vec[i]){mx2=mx1;mx1=vec[i];}
}
if(mx2==-1) return itr;
if(mx3==-1) return max(itr,mx1+mx2+l);
return max(itr,max(mx1+mx2+l,mx2+mx3+l*2));
}
