#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
int pa[100100], mx1[100100], mx2[100100], dpn[100100], dpc[100100], rtc[100100];
vector<pair<int, int>> g[100100];
bool visit[100100];
int fp(int u)
{
return (u == pa[u]) ? u : pa[u] = fp(pa[u]);
}
void dfs(int u)
{
visit[u] = true;
for(auto x : g[u])
{
if(visit[x.first]) continue;
dfs(x.first);
if(mx1[x.first] + x.second >= mx1[u])
{
mx2[u] = mx1[u];
mx1[u] = mx1[x.first] + x.second;
}
else if(mx1[x.first] + x.second > mx2[u])
{
mx2[u] = mx1[x.first] + x.second;
}
}
}
void compute(int u, int p, int w)
{
dpn[u] = max(w, mx1[u]);
if(dpc[fp(u)] > dpn[u])
{
dpc[fp(u)] = dpn[u];
rtc[fp(u)] = u;
}
for(auto x : g[u])
{
if(x.first == p) continue;
int ww = w + x.second;
if(mx1[x.first] + x.second == mx1[u]) ww = max(ww, mx2[u]+x.second);
else ww = max(ww, mx1[u]+x.second);
compute(x.first, u, ww);
}
}
int solve(int N)
{
for(int i=0 ; i<N ; i++)
{
visit[i] = false;
pa[i] = i;
mx1[i] = mx2[i] = dpn[i] = 0;
}
dfs(0);
compute(0, -1, 0);
int ret = 0;
for(int i=0 ; i<N ; i++)
ret = max(ret, dpn[i]);
return ret;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
for(int i=0 ; i<N ; i++)
{
pa[i] = i;
dpc[i] = 1e9;
}
for(int i=0 ; i<M ; i++)
{
g[A[i]].push_back({B[i], T[i]});
g[B[i]].push_back({A[i], T[i]});
pa[fp(A[i])] = fp(B[i]);
}
for(int i=0 ; i<N ; i++)
{
if(visit[i]) continue;
dfs(i);
compute(i, -1, 0);
}
int mx = 0, root = 0;
for(int i=0 ; i<N ; i++)
{
if(dpc[fp(i)] > mx)
{
mx = dpc[fp(i)];
root = rtc[fp(i)];
}
}
for(int i=0 ; i<N ; i++)
{
if(rtc[fp(i)] == root || !visit[fp(i)]) continue;
visit[fp(i)] = false;
g[root].push_back({rtc[fp(i)], L});
g[rtc[fp(i)]].push_back({root, L});
}
return solve(N);
}
