#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int MAXN = 2e5 + 5;
int par[MAXN];
int find(int u)
{
return u == par[u] ? u : par[u] = find(par[u]);
}
void join(int a, int b)
{
par[find(a)] = find(b);
}
int travelTime(int n, int m, int l, int A[], int B[], int T[])
{
iota(par, par + n, 0);
vector<vector<pair<int, int>>> adj(n);
for (int i = 0; i < m; i++)
{
int u = A[i];
int v = B[i];
int w = T[i];
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
join(u, v);
}
vector<int> f(n), s(n), g(n);
function<void(int, int)> down_dfs = [&](int u, int p)
{
for (auto v : adj[u])
{
if (v.first == p) continue;
down_dfs(v.first, u);
int k = f[v.first] + v.second;
if (k > f[u])
{
s[u] = f[u];
f[u] = k;
}
else if (k > s[u])
{
s[u] = k;
}
}
};
function<void(int, int)> up_dfs = [&](int u, int p)
{
for (auto v : adj[u])
{
if (v.first == p) continue;
if (f[u] == f[v.first] + v.second)
{
g[v.first] = max(g[u], s[u]) + v.second;
}
else
{
g[v.first] = max(g[u], f[u]) + v.second;
}
up_dfs(v.first, u);
}
};
vector<int> sz;
for (int i = 0; i < n; i++)
{
if (i == find(i))
{
down_dfs(i, -1);
up_dfs(i, -1);
}
}
vector<int> mn(n, INT_MAX);
for (int i = 0; i < n; i++)
{
int k = find(i);
mn[k] = min(mn[k], max(f[i], g[i]));
}
for (int i = 0; i < n; i++)
{
if (i == find(i)) sz.push_back(mn[i]);
}
sort(sz.rbegin(), sz.rend());
if (m + 1 == n)
{
int ans = 0;
for (int i = 0; i < n; i++) ans = max(ans, max(s[i], g[i]) + f[i]);
return ans;
}
else if (m + 2 == n)
{
int ans = 0;
for (int i = 0; i < n; i++) ans = max(ans, max(s[i], g[i]) + f[i]);
ans = max(ans, sz[0] + sz[1] + l);
return ans;
}
else
{
int ans = 0;
for (int i = 0; i < n; i++) ans = max(ans, max(s[i], g[i]) + f[i]);
ans = max(ans, sz[0] + sz[1] + l);
ans = max(ans, sz[1] + sz[2] + 2 * l);
return ans;
}
}
