#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int INF=(1e9+5);
vector<vector<pair<int,int> > > vec;
bitset<100001> vis;
int maxi[100001],h,d;
vector<int> f;
void dfs(int node){
vis[node]=1;
for(auto it:vec[node])
if(!vis[it.fi]){
dfs(it.fi);
maxi[node]=max(maxi[node],maxi[it.fi]+it.se);
}
}
void solve(int node,int p){
h=min(h,maxi[node]);
vector<int> g;
for(auto it:vec[node])
g.push_back(maxi[it.fi]+it.se);
sort(g.begin(),g.end(),greater<int>());
if(g.size()>1)d=max(d,g[0]+g[1]);
else if(g.size()==1)d=max(d,g[0]);
for(auto it:vec[node])
if(it.fi!=p){
int o=maxi[node],o2=maxi[it.fi];
if(g.size()>1&&g[0]==(maxi[it.fi]+it.se))
maxi[node]=g[1];
else if(g.size()==1)maxi[node]=0;
maxi[it.fi]=max(maxi[it.fi],maxi[node]+it.se);
solve(it.fi,node);
maxi[node]=o,maxi[it.fi]=o2;
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
vec.resize(N);
for (int i = 0; i < M; ++i)
{
vec[A[i]].push_back({B[i],T[i]});
vec[B[i]].push_back({A[i],T[i]});
}
int ans=0;
for (int i = 0; i < N; ++i)
{
if(!vis[i]){
dfs(i);
h=INF,d=0,solve(i,i);
f.push_back(h),ans=max(d,ans);
}
}
sort(f.begin(),f.end(),greater<int>());
if(f.size()>1)ans=max(ans,f[0]+f[1]+L);
if(f.size()>2)ans=max(ans,f[1]+f[2]+2*L);
return ans;
}
