#include<bits/stdc++.h>
#include "dreaming.h"
#define endl '\n'
using namespace std;
const long long maxn=1e5+10;
long long n,m,l,leader;
long long dp[maxn],f[maxn],s[maxn];
bool used[maxn];
long long minn;
struct c
{
long long x,t;
};
vector<c> v[maxn];
vector<pair<long long,long long>> leaders;
void dfs(long long i,long long par)
{
used[i]=1;
dp[i]=0;
for(auto nb:v[i])
{
if(nb.x==par) continue;
dfs(nb.x,i);
dp[i]=max(dp[i],dp[nb.x]+nb.t);
}
}
void dfs1(long long i,long long par,long long t)
{
dp[i]=max(dp[i],t);
if(dp[i]<minn)
{
minn=dp[i];
leader=i;
}
vector<long long> val;
vector<c> child;
for(auto nb:v[i])
{
if(nb.x==par) continue;
child.push_back(nb);
val.push_back(dp[nb.x] + nb.t);
}
int sz = val.size();
vector<long long> pref(sz), suf(sz);
for(int j=0; j<sz; j++)
{
pref[j]=val[j];
if(j) pref[j]=max(pref[j],pref[j-1]);
}
for(int j=sz-1; j>=0; j--)
{
suf[j]=val[j];
if(j+1<sz) suf[j]=max(suf[j],suf[j+1]);
}
for(int j=0; j<sz; j++)
{
auto nb = child[j];
long long best = t;
if(j) best=max(best,pref[j-1]);
if(j+1<sz) best=max(best,suf[j+1]);
dfs1(nb.x,i,best+nb.t);
}
}
int travelTime(int N, int M, int L,int A[], int B[], int T[])
{
n=N;
m=M;
l=L;
for(long long i=0; i<m; i++)
{
v[A[i]].push_back({B[i],T[i]});
v[B[i]].push_back({A[i],T[i]});
}
for(long long i=0; i<n; i++)
{
if(used[i]==0)
{
leader=i;
minn=1e18;
dfs(i,-1);
dfs1(i,-1,0);
leaders.push_back({minn,leader});
}
}
sort(leaders.begin(),leaders.end());
reverse(leaders.begin(),leaders.end());
for(auto i:leaders)
{
if(i.second==leaders[0].second) continue;
v[i.second].push_back({leaders[0].second,l});
v[leaders[0].second].push_back({i.second,l});
}
for(long long i=0; i<n; i++)
{
dp[i]=f[i]=s[i]=0;
}
minn=1e18;
leader=0;
dfs(0,-1);
dfs1(0,-1,0);
long long ans=0;
for(long long i=0; i<n; i++)
{
ans=max(ans,dp[i]);
}
return ans;
}
