#include<bits/stdc++.h>
#include "dreaming.h"
#define endl '\n'
using namespace std;
const int maxn=1e5+10;
int n,m,l,leader;
int dp[maxn],f[maxn],s[maxn];
bool used[maxn];
long long minn;
struct c
{
int x,t;
};
vector<c> v[maxn];
vector<pair<long long,int>> leaders;
void dfs(int i,int par)
{
used[i]=1;
int sm=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);
}
for(auto nb:v[i])
{
if(nb.x==par)
{
continue;
}
if(dp[nb.x]+nb.t==dp[i])
{
f[i]=nb.x;
}
else
{
if(dp[nb.x]+nb.t>s[i])
{
s[i]=dp[nb.x]+nb.t;
}
}
}
}
void dfs1(int i,int par,int t)
{
dp[i]=max(dp[i],t);
if(dp[i]<minn)
{
minn=dp[i];
leader=i;
}
for(auto nb:v[i])
{
if(nb.x==par)
{
continue;
}
if(nb.x==f[i])
{
dfs1(nb.x,i,max(t,s[i])+nb.t);
}
else
{
dfs1(nb.x,i,max(t,dp[i])+nb.t);
}
}
}
int travelTime(int N, int M, int L,int A[], int B[], int T[])
{
n=N;
m=M;
l=L;
for(int i=0;i<m;i++)
{
v[A[i]].push_back({B[i],T[i]});
v[B[i]].push_back({A[i],T[i]});
}
for(int 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(int i=0;i<n;i++)
{
dp[i]=f[i]=s[i]=0;
}
minn=1e18;
leader=0;
dfs(0,-1);
dfs1(0,-1,0);
int ans=0;
for(int i=1;i<=n;i++)
{
ans=max(ans,dp[i]);
}
return ans;
}
