#include "dreaming.h"
#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<ll,ll>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5;
const ll inf=1e18;
const ll mod=1e9+7;
ll lab[maxN];
ll findset(ll x)
{
return lab[x]<0?x:lab[x]=findset(lab[x]);
}
void unite(ll u,ll v)
{
u=findset(u);
v=findset(v);
if(u==v) return;
if(lab[u]>lab[v]) swap(u,v);
lab[u]+=lab[v];
lab[v]=u;
}
vector<pli>g[maxN];
ll n,m;
vector<ll>vec[maxN];
ll h[maxN][3];
void dfs(ll u,ll p,ll t)
{
for(auto zz:g[u])
{
if(zz.fi!=p)
{
h[zz.fi][t]=h[u][t]+zz.se;
dfs(zz.fi,u,t);
}
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
n=N,m=M;
for(int i=0;i<N;i++) lab[i]=-1;
for(int i=0;i<M;i++)
{
unite(A[i],B[i]);
g[A[i]].pb({B[i],T[i]});
g[B[i]].pb({A[i],T[i]});
}
for(int i=0;i<n;i++)
{
vec[findset(i)].pb(i);
}
ll ans=0;
vector<pli>cc;
for(int i=0;i<n;i++)
{
if(findset(i)==i)
{
dfs(i,i,0);
ll mx=-1,id=0;
for(auto u:vec[i])
{
if(h[u][0]>mx)
{
mx=h[u][0];
id=u;
}
}
dfs(id,id,1);
mx=-1,id=0;
for(auto u:vec[i])
{
if(h[u][1]>mx)
{
mx=h[u][1];
id=u;
}
}
ans=max(ans,mx);
dfs(id,id,2);
mx=inf,id=0;
for(auto u:vec[i])
{
if(max(h[u][1],h[u][2])<mx)
{
mx=max(h[u][1],h[u][2]);
id=u;
}
}
cc.pb({mx,id});
}
}
sort(cc.begin(),cc.end(),greater<pli>());
ll dm=inf;
for(int i=0;i<cc.size();i++)
{
ll mx1=-inf,mx2=-inf;
for(int j=0;j<cc.size();j++)
{
if(j==i) continue;
if(mx1==-inf)
{
mx1=cc[j].fi;
}
else if(mx2==-inf) mx2=cc[j].fi;
if(mx2!=-inf) break;
}
dm=min(dm,max(mx1+mx2+2*L,cc[i].fi+mx1+L));
}
ans=max(ans,dm);
return ans;
}
/*void solve()
{
cout << travelTime(12,8,2,{0, 8, 2, 5, 5, 1, 1, 10},{8, 2, 7, 11, 1, 3, 9, 6},{4, 2, 4, 3, 7, 1, 5, 3});
}
int main()
{
fastio
//freopen(TASKNAME".INP","r",stdin);
//freopen(TASKNAME".OUT","w",stdout);
solve();
}*/
