#include "dreaming.h"
#include<algorithm>
#include<vector>
using namespace std;
int maxx,t,dap,s[100010],w,arr[200010],top,ch[100010],pos[100010],big1[100010],big2[100010];
vector<int>d[100010];
struct data{
int x,y,c;
bool operator<(const data&r)const{
return x<r.x;
}
}con[200010];
void dfs1(int x,int cost)
{
int i;
ch[x]=1;
if(maxx<cost) maxx=cost, t=x;
for(i=pos[x];;i++)
{
if(x!=con[i].x) break;
if(ch[con[i].y]) continue;
dfs1(con[i].y,cost+con[i].c);
d[x].push_back(big1[con[i].y]+con[i].c);
}
int p=0;
for(i=0;i<d[x].size();i++){
if(big1[x]<d[x][i]){big1[x]=d[x][i]; p=i;}
}
for(i=0;i<d[x].size();i++){
if(big2[x]<d[x][i] && i!=p) big2[x]=d[x][i];
}
}
void dfs2(int x,int gap)
{
int i;
ch[x]=2;
if(dap>max(big1[x],gap)) dap=max(big1[x],gap);
for(i=pos[x];;i++)
{
if(x!=con[i].x) break;
if(ch[con[i].y]==2) continue;
int maxi=0;
if(big1[x]==d[x][s[x]]) maxi=max(gap,big2[x]);
else maxi=max(gap,big1[x]);
dfs2(con[i].y,maxi+con[i].c);
s[x]++;
}
}
void dfs(int x,int cost)
{
int i;
ch[x]=3;
if(maxx<cost) maxx=cost, t=x;
for(i=pos[x];;i++)
{
if(x!=con[i].x) break;
if(ch[con[i].y]==3) continue;
dfs(con[i].y,cost+con[i].c);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
int i,ans=0;
for(i=0;i<M;i++)
{
A[i]++; B[i]++;
w++; con[w].x=A[i]; con[w].y=B[i]; con[w].c=T[i];
w++; con[w].x=B[i]; con[w].y=A[i]; con[w].c=T[i];
}
sort(con+1,con+w+1);
for(i=1;i<=w;i++)
{
if(con[i].x!=con[i-1].x) pos[con[i].x]=i;
}
for(i=1;i<=N;i++)
{
if(ch[i]==0)
{
dap=2147483647; maxx=0;
dfs1(i,0);
dfs2(i,0);
maxx=0; dfs(t,0);
if(ans<maxx) ans=maxx;
arr[++top]=dap;
}
}
sort(arr+1,arr+top+1);
if(top==1) return ans;
if(top==2) return max(ans,arr[1]+arr[2]+L);
return max(ans,max(arr[top]+arr[top-1]+L,arr[top-1]+arr[top-2]+L*2));
}
