#include "dreaming.h"
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
ll n = N, m = M, l = L;
vector e(n, vector<pii>());
vector<int> par(n, -1);
vector<bool> v(n, false);
vector<ll> dist(n, 0);
for (int i = 0; i < m; i++) {
e[A[i]].push_back({B[i], T[i]});
e[B[i]].push_back({A[i], T[i]});
}
ll ans = 0;
vector<ll> a;
for (int c = 0; c < n; c++) {
if (v[c])
continue;
vector<ll> comp;
bool push_comp = true;
auto dfs_1 = [&](auto &dfs, int g, int p, ll d) -> void {
dist[g] = d;
v[g] = true;
par[g] = p;
if (push_comp) {
comp.push_back(g);
}
for (auto [u, xd] : e[g]) {
if (u == p)
continue;
dfs(dfs, u, g, d + xd);
}
};
dfs_1(dfs_1, c, -1, 0);
ll max_dist = 0, root = c;
for (auto u : comp) {
if (dist[u] > max_dist) {
max_dist = dist[u];
root = u;
}
}
push_comp = false;
dfs_1(dfs_1, root, -1, 0);
max_dist = 0;
int root_2 = root;
for (auto u : comp) {
if (dist[u] > max_dist) {
max_dist = dist[u];
root_2 = u;
}
}
int cur = root_2;
ll h = max_dist;
while (par[cur] != -1) {
ll d1 = dist[cur], d2 = max_dist - dist[cur];
h = min(h, max(d1, d2));
cur = par[cur];
}
ans = max(ans, max_dist);
a.push_back(h);
}
sort(a.begin(), a.end(), greater<ll>());
if ((int)a.size() >= 2) {
ans = max(ans, a[0] + a[1] + L);
}
if ((int)a.size() >= 3) {
ans = max(ans, a[1] + a[2] + 2 * L);
}
return ans;
}
