#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
const int maxn=1e5+5;
vector<pair<int,int>>adj[maxn];
vector<int>d(maxn),ver;
vector<bool>used(maxn);
int dist,mx,vr[3];
void dfs(int x,int p,int e){
used[x]=true;
if(e==0){
ver.pb(x);
}
if(dist>mx){
mx=dist;
vr[e]=x;
}
for(auto [y,w]:adj[x]){
if(y!=p){
dist+=w;
dfs(y,x,e);
dist-=w;
}
}
}
void calc(int x,int p){
d[x]=max(d[x],dist);
mx=max(mx,dist);
for(auto [y,w]:adj[x]){
if(y!=p){
dist+=w;
calc(y,x);
dist-=w;
}
}
}
int travelTime(int N,int M,int L,int A[],int B[],int T[]){
for(int i=0;i<M;i++){
adj[A[i]].pb({B[i],T[i]});
adj[B[i]].pb({A[i],T[i]});
}
vector<int>v,u;
for(int i=0;i<N;i++){
if(!used[i]){
ver.clear();
mx=-1,dist=0;
dfs(i,-1,0);
mx=-1,dist=0;
dfs(vr[0],-1,1);
mx=0,dist=0;
calc(vr[0],-1);
mx=0,dist=0;
calc(vr[1],-1);
v.pb(mx);
int mn=1e9;
for(auto j:ver){
mn=min(mn,d[j]);
}
u.pb(mn);
}
}
if(v.size()==1){
return v[0];
}
if(v.size()==2){
return max({v[0],v[1],u[0]+u[1]+L});
}
int D=0,ans=1e9;
for(auto x:v){
D=max(D,x);
}
multiset<int,greater<int>>st;
for(auto x:u){
st.insert(x);
}
for(auto x:u){
st.erase(st.find(x));
auto it=st.begin();
it++;
ans=min(ans,max(x+*st.begin()+L,*st.begin()+*it+2*L));
st.insert(x);
}
ans=max(ans,D);
return ans;
}
