#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include "dreaming.h"
using namespace std;
const int N = 3e5+1;
vector<pair<int, int>> g[N];
int dp[N];
int depth[N];
int mx[N];
bool vis[N];
int dp1[N];
int dp2[N];
int h[N];
vector<int> gag[N];
int o;
vector<pair<int,int>> hert;
void dfs2(int v,int p) {
mx[v] = depth[v];
for (auto i : g[v]) {
if (i.first == p) {
continue;
}
depth[i.first] = depth[v] + i.second;
dfs2(i.first,v);
mx[v] = max(mx[i.first], mx[v]);
}
dp[v] = mx[v] - depth[v];
vector<int> mas;
for (auto i : g[v]) {
if (i.first == p) {
continue;
}
mas.push_back(mx[i.first]);
}
if (mas.empty() || mas.size()==1) {
return;
}
sort(mas.rbegin(), mas.rend());
dp[v] = max(dp[v],mas[0] + mas[1] - 2*depth[v]);
}
int get() {
for (int i = 0;i < o;++i) {
dp[i] = 0;
mx[i] = 0;
depth[i] = 0;
}
dfs2(0,-1);
int answ = 0;
for (int i = 0;i < o;++i) {
answ = max(answ, dp[i]);
}
return answ;
}
void dfs(int v,int comp) {
vis[v] = 1;
gag[comp].push_back(v);
for (auto i : g[v]) {
if (!vis[i.first]) {
dfs(i.first, comp);
}
}
}
void dfs3(int v,int p) {
for (auto i : g[v]) {
if (i.first == p) {
continue;
}
h[i.first] = h[v] + i.second;
dfs3(i.first, v);
dp1[v] = max(dp1[v],dp1[i.first]+i.second);
}
}
void dfs4(int v, int p) {
multiset<int, greater<int>> st;
for (auto i : g[v]) {
if (i.first == p) {
continue;
}
dp2[i.first] = dp2[v] + i.second;
st.insert(dp1[i.first]+i.second);
}
for (auto i : g[v]) {
if (i.first == p) {
continue;
}
auto j = st.find(dp1[i.first]+i.second);
st.erase(j);
if (!st.empty()) {
dp2[i.first] = max(dp2[i.first], *st.begin() + i.second);
}
st.insert(dp1[i.first]+i.second);
}
for (auto i : g[v]) {
if (i.first == p) {
continue;
}
dfs4(i.first, v);
}
}
int travelTime(int n, int m, int l,
int a[], int b[], int t[]) {
o = n;
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] });
}
int cnt = 0;
for (int i = 0;i < n;++i) {
if (!vis[i]) {
dfs(i, cnt);
++cnt;
}
}
vector<int> px(n + 1);
int mn_id = 0;
int ans = 0;
for (int j = 0;j < cnt;++j) {
dfs3(gag[j][0], -1);
dfs4(gag[j][0],-1);
int p1;
int answ = 1e9;
for (auto i : gag[j]) {
int x = max(dp1[i], dp2[i]);
if (x < answ) {
answ = x;
p1 = i;
}
}
if (answ > ans) {
ans = answ;
mn_id = p1;
}
px[j] = p1;
}
for (int i = 0;i < cnt;++i) {
if (px[i] != mn_id) {
g[px[i]].push_back({ mn_id,l });
g[mn_id].push_back({ px[i], l});
}
}
return get();
}
