#include <bits/stdc++.h>
#ifndef ARTHUR_LOCAL
#include "dreaming.h"
#endif
using namespace std;
using pii=pair<int,int>;
#define ff first
#define ss second
const int MAXN = 100001;
vector<pii> adj[MAXN];
bool vis[MAXN];
int dis[MAXN];
pii antipode={-1,-1};
bool vis2[MAXN];
int dis2[MAXN];
pii antipode2={-1,-1};
bool vis3[MAXN];
int semi_diam = -1;
void dfs1(int v)
{
vis[v]=1;
for(auto u_raw:adj[v])
{
int u=u_raw.ff;
int d=u_raw.ss;
if(vis[u]) continue;
dis[u]=dis[v]+d;
antipode=max(antipode,{dis[u],u});
dfs1(u);
}
}
void dfs2(int v)
{
vis2[v]=1;
for(auto u_raw:adj[v])
{
int u=u_raw.ff;
int d=u_raw.ss;
if(vis2[u]) continue;
dis2[u]=dis2[v]+d;
antipode2=max(antipode2,{dis2[u],u});
dfs2(u);
}
}
void dfs3(int v)
{
vis3[v]=1;
for(auto u_raw:adj[v])
{
int u=u_raw.ff;
int d=u_raw.ss;
if(vis3[u]) continue;
semi_diam = min(semi_diam,max(antipode2.ff-dis2[u],dis2[u]));
dfs3(u);
}
}
int travelTime(int n, int m, int l, int A[], int B[], int T[])
{
vector<pii> di_sdi; // all the diameter, semi-diameter pairs
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(vis[i]) continue;
dfs1(i);
if(antipode == make_pair(-1,-1))
{
di_sdi.push_back({0,0});
continue;
}
dfs2(antipode.ss);
// cout << i << " " << antipode.ss << " " << antipode2.ss << " " << antipode2.ff << endl;
semi_diam=int(1e9);
dfs3(antipode.ss); // don't think that this need be from antipode2.ss
di_sdi.push_back({semi_diam,antipode2.ff});
antipode={-1,-1};
antipode2={-1,-1};
}
// for(auto SD:di_sdi)
// {
// cout << SD.ff << " " << SD.ss << endl;
// }
sort(di_sdi.rbegin(),di_sdi.rend());
int ans=0;
for(auto SD:di_sdi) ans=max(ans,SD.ss);
if(di_sdi.size()>=3) ans=max(ans,l+l+di_sdi[1].ff+di_sdi[2].ff);
if(di_sdi.size()>=2) ans=max(ans,l+di_sdi[0].ff+di_sdi[1].ff);
// cout << ans << endl;
return ans;
}
