#include "dreaming.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;
#define MAX_N 100000
struct S{
int x, y;
};
vector<S> gp[MAX_N+1];
int ans = 0;
bool vst[MAX_N+1];
vector<int> v;
int k1, k2;
bool vst11[MAX_N+1], vst12[MAX_N+1];
void dfs11(int x, int y){
vst11[x] = true;
if(k1<y){
k1 = y; k2 = x;
}
for(int i=0; i<gp[x].size(); i++){
if(!vst11[gp[x][i].x]) dfs11(gp[x][i].x, y+gp[x][i].y);
}
}
void dfs12(int x, int y){
vst12[x] = true;
if(k1<y){
k1 = y; k2 = x;
}
for(int i=0; i<gp[x].size(); i++){
if(!vst12[gp[x][i].x]) dfs12(gp[x][i].x, y+gp[x][i].y);
}
}
int dist[MAX_N+1];
bool vst21[MAX_N+1];
void dfs21(int x){
dist[x] = 0;
vst21[x] = true;
for(int i=0; i<gp[x].size(); i++){
if(!vst21[gp[x][i].x]){
dfs21(gp[x][i].x);
dist[x] = max(dist[x], dist[gp[x][i].x]+gp[x][i].y);
}
}
return;
}
bool vst22[MAX_N+1];
int dfs22(int x, int y){
vst22[x] = true;
int t1=0, t2=0, idx, t3;
for(int i=0; i<gp[x].size(); i++){
if(!vst22[gp[x][i].x]){
if(t1<dist[gp[x][i].x] + gp[x][i].y){
t2 = t1;
t1 = dist[gp[x][i].x] + gp[x][i].y;
t3 = gp[x][i].y;
idx = gp[x][i].x;
}
else if(t2<dist[gp[x][i].x] + gp[x][i].y){
t2 = dist[gp[x][i].x] + gp[x][i].y;
}
}
}
if(t1==0){
return y;
}
//cout<<x<<' '<<y<<' '<<t1<<' '<<t2<<' '<<t3<<endl;
return min(max(y, t1), dfs22(idx, max(y, t2)+t3));
}
void dfs1(int x){
k1 = 0; k2 = x;
dfs11(x, 0);
k1 = 0;
dfs12(k2, 0);
ans = max(ans, k1);
dfs21(x);
v.push_back(dfs22(x, 0));
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(int i=0; i<M; i++){
gp[A[i]].push_back({B[i], T[i]});
gp[B[i]].push_back({A[i], T[i]});
}
for(int i=0; i<N; i++){
if(!vst11[i]){
dfs1(i);
}
}
sort(v.begin(), v.end());
/*for(int i=0; i<v.size(); i++){
printf("%d ",v[i]);
}*/
if(v.size()>=2){
ans = max(ans, v[v.size()-1]+v[v.size()-2]+L);
}
if(v.size()>=3){
ans = max(ans, v[v.size()-2]+v[v.size()-3]+2*L);
}
return ans;
}
