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