#include "dreaming.h"
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
int cnt, root[100005], dpdown[100005][3], dpup[100005], maxdiam, minv[100005];
vector< pair<int, int> > adj[100005];
bool visited[100005];
void dfsdown(int v, int prev){
visited[v] = true;
for(int i=0; i<adj[v].size(); i++){
int next = adj[v][i].first;
int time = adj[v][i].second;
if(next == prev) continue;
dfsdown(next,v);
int weight = dpdown[next][0] + time;
if(dpdown[v][0] < weight){
dpdown[v][1] = dpdown[v][0];
dpdown[v][0] = weight;
dpdown[v][2] = next;
}
else if(dpdown[v][1] < weight && weight < dpdown[v][0]) dpdown[v][1] = weight;
}
}
void dfsup(int v, int prev, int w){
dpup[v] = w;
for(int i=0; i<adj[v].size(); i++){
int next = adj[v][i].first;
int time = adj[v][i].second;
if(next == prev) continue;
if(next == dpdown[v][2]) dfsup(next,v,max(dpdown[v][1],w)+time);
else dfsup(next,v,max(dpdown[v][0],w)+time);
}
}
void dfsfinal(int v, int prev){
maxdiam = max(maxdiam,max(dpdown[v][0],dpup[v]));
if(dpdown[v][0] != 0 && dpup[v] != 0) minv[cnt] = min(minv[cnt],max(dpup[v],dpdown[v][0]));
else if(dpdown[v][0] != 0) minv[cnt] = min(minv[cnt],dpdown[v][0]);
else if(dpup[v] != 0) minv[cnt] = min(minv[cnt],dpup[v]);
for(int i=0; i<adj[v].size(); i++){
int next = adj[v][i].first;
if(next == prev) continue;
dfsfinal(next,v);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(int i=0; i<M; i++){
adj[A[i]].push_back(make_pair(B[i],T[i]));
adj[B[i]].push_back(make_pair(A[i],T[i]));
}
for(int i=0; i<N; i++){
if(!visited[i]){
cnt++;
root[cnt] = i;
dfsdown(i,-1);
dfsup(i,-1,0);
minv[cnt] = dpdown[i][0];
dfsfinal(i,-1);
}
}
// for(int i=1; i<=cnt; i++) printf("%d ",minv[i]);
sort(minv+1,minv+cnt+1);
// for(int i=1; i<=cnt; i++) printf("%d ",minv[i]);
// for(int i=0; i<N; i++) printf("%d) %d %d %d %d\n",i,dpdown[i][0],dpdown[i][1],dpdown[i][2],dpup[i]);
if(cnt == 1) return maxdiam;
if(cnt == 2) return max(maxdiam, minv[cnt]+minv[cnt-1]+L);
return max(maxdiam, max(minv[cnt]+minv[cnt-1]+L,minv[cnt-1]+minv[cnt-2]+2*L));
// for(int i=0; i<N; i++) printf("%d) %d %d %d %d\n",i,dpdown[i][0],dpdown[i][1],dpdown[i][2],dpup[i]);
}
