#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
const int n = 100000;
int par[n], dep[n], dia[n], ans[n];
vector<pair<int, int>> adj[n];
int fp(int x) {
if (par[x] == -1) return x;
return par[x] = fp(par[x]);
}
int dfs1(int x, int p) {
int mx = 0;
for (auto &[u, w] : adj[x]) {
if (u == p) continue;
mx = max(mx, w + dfs1(u, x));
}
return dep[x] = mx;
}
void dfs2(int x, int p, int v) {
ans[x] = max(dep[x], v);
if (adj[x].empty()) return;
int k = adj[x].size();
vector<int> tmp(k, 0), pfx(k, 0), sfx(k, 0);
for (int i = 0; i < k; i++) {
auto &[u, w] = adj[x][i];
if (u == p) continue;
tmp[i] = w + dep[u];
}
pfx[0] = tmp[0], sfx[k-1] = tmp[k-1];
for (int i = 1; i < k; i++) pfx[i] = max(pfx[i-1], tmp[i]);
for (int i = k-2; i >= 0; i--) sfx[i] = max(sfx[i+1], tmp[i]);
for (int i = 0; i < k; i++) {
auto &[u, w] = adj[x][i];
if (u == p) continue;
int mx = v;
if (i > 0) mx = max(mx, pfx[i-1]);
if (i < k-1) mx = max(mx, sfx[i+1]);
dfs2(u, x, mx + w);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
memset(par, -1, sizeof(par));
vector<bool> rt(N, false);
vector<int> mn(N, INT_MAX), l;
for (int i = 0; i < M; i++) {
adj[A[i]].emplace_back(B[i], T[i]);
adj[B[i]].emplace_back(A[i], T[i]);
int pa = fp(A[i]), pb = fp(B[i]);
par[pa] = pb;
}
for (int i = 0; i < N; i++) rt[fp(i)] = true;
for (int i = 0; i < N; i++) {
if (!rt[i]) continue;
dfs1(i, -1);
dfs2(i, -1, 0);
}
int mx = 0;
for (int i = 0; i < N; i++) mn[fp(i)] = min(mn[fp(i)], ans[i]), dia[fp(i)] = max(dia[fp(i)], ans[i]);
for (int i = 0; i < N; i++) {
if (!rt[i]) continue;
mx = max(mx, dia[i]);
l.emplace_back(mn[i]);
}
mx = max(mx, l[0]);
sort(l.rbegin(), l.rend());
if (l.size() >= 2) mx = max(mx, l[0] + l[1] + L);
if (l.size() >= 3) mx = max(mx, l[1] + l[2] + 2 * L);
return mx;
}
