#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
// #define int long long
#define ar array
#define db double
#define sz(x) (int)x.size()
const db pi = acos(-1);
const int mxn = 1e5 + 7;
int in[mxn], out[mxn];
int vis[mxn];
vector<ar<int, 2> > g[mxn];
int tmp, node;
int d(int u)
{
return in[u] + out[u];
}
int leaf(int u)
{
return max(in[u], out[u]);
}
void dfs(int u)
{
vis[u] = 1;
for (auto [v, w] : g[u])
{
if (vis[v]) continue;
dfs(v);
in[u] = max(in[u], in[v] + w);
}
}
void dfs2(int u, int p)
{
int mx1 = 0, mx2 = 0;
for (auto [v, w] : g[u])
{
if (v == p) continue;
if (in[v] + w > mx1) mx2 = mx1, mx1 = in[v] + w;
else mx2 = max(mx2, in[v] + w);
}
for (auto [v, w] : g[u])
{
if (v == p) continue;
if (in[v] + w == mx1) out[v] = max(out[u], mx2) + w;
else out[v] = max(out[u], mx1) + w;
dfs2(v, u);
}
if (tmp > leaf(u))
{
tmp = leaf(u);
node = u;
}
}
int travelTime(int n, int m, int l, int a[], int b[], int t[])
{
for (int i = 0; i < m; i++)
{
g[a[i] + 1].push_back({b[i] + 1, t[i]});
g[b[i] + 1].push_back({a[i] + 1, t[i]});
}
vector<int> ans;
int mx = 0;
for (int i = 1; i <= n; i++)
if (!vis[i])
{
tmp = mxn;
dfs(i);
dfs2(i, i);
ans.push_back(node);
mx = max(mx, d(node));
// cout << i - 1 << ' ' << tmp << '\n';
}
sort(ans.begin(), ans.end(), [](int u, int v)
{
return leaf(u) > leaf(v);
});
if (sz(ans) >= 2) mx = max(mx, leaf(ans[0]) + leaf(ans[1]) + l);
if (sz(ans) >= 3) mx = max(mx, leaf(ans[1]) + leaf(ans[2]) + 2 * l);
return mx;
};
// int n, m, l;
// int a[mxn], b[mxn], t[mxn];
// signed main()
// {
// ios::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
// // De nghi ko bat ultra instinct tay nhanh hon nao luc lam bai
// cin >> n >> m >> l;
// for (int i = 0; i < m; i++)
// {
// cin >> a[i] >> b[i] >> t[i];
// }
// cout << travelTime(n, m, l, a, b, t);
// /*
// 12 8 2
// 0 8 4
// 8 2 2
// 2 7 4
// 5 11 3
// 5 1 7
// 1 3 1
// 1 9 5
// 10 6 3*/
// return 0;
// }
