#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
vector <pair <int, int>> ke[100001];
int dp[100001],dp2[100001],ch[100001],mx;
void dfs(int u, int p){
ch[u]=1;
for (auto [v,w]:ke[u])
if (v!=p){
dfs(v,u);
dp[u]=max(dp[u],dp[v]+w);
}
}
void dfs2(int u, int p){
ch[u]=0;
int mx=0,idx=-1,mx2=0;
for (auto [v,w]:ke[u]){
if (v==p)
continue;
if (dp[v]+w>mx){
mx2=mx;
mx=dp[v]+w;
idx=v;
}
else
mx2=max(mx2,dp[v]+w);
}
for (auto [v,w]:ke[u]){
if (v==p)
continue;
dp2[v]=max(dp2[u],(v==idx?mx2:mx))+w;
dfs2(v,u);
}
}
int dfs3(int u, int p){
ch[u]=1;
int mn=dp[u];
for (auto [v,w]:ke[u])
if (v!=p)
mn=min(mn,dfs3(v,u));
return mn;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for (int i=0;i<M;i++){
ke[A[i]].emplace_back(B[i],T[i]);
ke[B[i]].emplace_back(A[i],T[i]);
}
for (int i=0;i<N;i++)
if (!ch[i])
dfs(i,i);
for (int i=0;i<N;i++)
if (ch[i])
dfs2(i,i);
for (int i=0;i<N;i++){
dp[i]=max(dp[i],dp2[i]);
mx=max(mx,dp[i]);
}
int x=-1e9,y=-1e9,z=-1e9;
for (int i=0;i<N;i++)
if (!ch[i]){
int val=dfs3(i,i);
if (x<val){
z=y;
y=x;
x=val;
}
else if (y<val){
z=y;
y=val;
}
else
z=max(z,val);
}
return max(mx,max(x+y+L,y+z+L*2));
}
