#include<bits/stdc++.h>
using namespace std;
#include "dreaming.h"
#define N 100005
int dep[N],ans;
vector<int> val;
vector<pair<int,int>> g[N];
pair<int,int> ma1[N],ma2[N];
bitset<N> vis;
int dfs(int s,int f){
vis[s]=true;
for(auto x:g[s]){
if(x.first==f)continue;
int d=dfs(x.first,s)+x.second;
pair<int,int> pa=make_pair(d,x.first);
if(pa>ma1[s])swap(pa,ma1[s]);
if(pa>ma2[s])swap(pa,ma2[s]);
dep[s]=max(dep[s],d);
}
ans=max(ans,ma1[s].first+ma2[s].first);
return dep[s];
}
int cal(int s,int f,int carry){
vis[s]=true;
int m;
m=max(carry,ma1[s].first);
for(auto x:g[s]){
if(x.first==f)continue;
if(ma1[s].second==x.first)m=min(m,cal(x.first,s,max(carry,ma2[s].first)+x.second));
else m=min(m,cal(x.first,s,max(carry,ma1[s].first)+x.second));
}
return m;
}
int travelTime(int n, int m, int l, int u[N], int v[N], int t[N]){
int i,a,b,w,com;
for(i=0;i<m;i++){
a=u[i],b=v[i],w=t[i];
g[a].push_back({b,w});
g[b].push_back({a,w});
}
com=n-m;
for(i=0;i<n;i++)ma1[i]=ma2[i]={0,-1};
for(i=0;i<n;i++)if(!vis[i])dfs(i,-1);
vis=0;
for(i=0;i<n;i++)if(!vis[i])val.push_back(cal(i,-1,0));
sort(val.begin(),val.end(),greater<int>());
if(val.size()>1)ans=max(ans,val[0]+val[1]+l);
if(val.size()>2)ans=max(ans,val[1]+val[2]+2*l);
return ans;
}
