#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
int mx[100005], mx2[100005];
bool vis[100005];
vector<pair<int, int>> adj[100005];
int dfs1(int u, int p) {
vis[u] = true;
mx[u] = mx2[u] = 0;
int ret = 0;
for (auto [v, w] : adj[u])
if (v != p) {
ret = max(ret, dfs1(v, u));
if (mx[v] + w >= mx[u]) {
mx2[u] = mx[u];
mx[u] = mx[v] + w;
} else if (mx[v] + w > mx2[u]) {
mx2[u] = mx[v] + w;
}
}
return max(ret, mx[u] + mx2[u]);
}
int dfs2(int u, int p) {
int ret = mx[u];
for (auto [v, w] : adj[u])
if (v != p) {
int memo = mx[v], memo2 = mx2[v], nxt = (mx[v] + w == mx[u] ? mx2[u] : mx[u]) + w;
if (nxt >= mx[v]) {
mx2[v] = mx[v];
mx[v] = nxt;
} else if (nxt > mx2[v]) {
mx2[v] = nxt;
}
ret = min(ret, dfs2(v, u));
mx[v] = memo;
mx2[v] = memo2;
}
return ret;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for (int i=0; i<N; i++) {
vis[i] = false;
adj[i].clear();
}
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]);
}
vector<pair<int, int>> comp;
for (int i=0; i<N; i++)
if (!vis[i]) {
int d = dfs1(i, -1), mxD = dfs2(i, -1);
comp.emplace_back(mxD, d);
}
sort(comp.rbegin(), comp.rend());
int ret = comp[0].second, mxD = comp[0].first;
for (int i=1; i<(int)comp.size(); i++) {
ret = max({ret, comp[i].first + mxD + L, comp[i].second});
mxD = max(mxD, comp[i].first + L);
}
return ret;
}
