"
#include "bits/stdc++.h"
using namespace std;
const int MXN = 1e5 + 5;
int64_t dist[10][MXN], far[MXN];
vector<array<int, 2>> adj[MXN];
vector<int> component;
bool vis[MXN];
void cdfs(const int &node, int par = 0) {
vis[node] = true, component.push_back(node);
for (auto &[child, cost] : adj[node]) if (child != par) cdfs(child, node);
}
void dfs(const int &node, const int &type, int par = 0) {
for (auto &[child, cost]: adj[node]) if (child != par)
dist[type][child] = dist[type][node] + cost, dfs(child, type, node);
}
int fun(const vector<int> &C, const int &n) {
if ((int)C.size() == 1) {
far[C[0]] = 0;
return C[0];
}
if ((int)C.size() == 2) {
int u = C[0], v = C[1];
for (auto &[node, cost] : adj[u]) if (node == v) {
far[v] = far[u] = cost;
break;
}
return C.back();
}
for (auto &c : C) dist[0][c] = dist[1][c] = dist[2][c] = 0;
dfs(C.back(), 0);
int64_t MAX = 0, MIN = INT_MAX;
int node1 = C.back(), node2 = C.back(), ans = C.back();
for (auto &c : C) if (dist[0][c] > MAX) MAX = dist[0][c], node1 = c;
dfs(node1, 1), MAX = 0;
for (auto &c : C) if (dist[1][c] > MAX) MAX = dist[1][c], node2 = c;
dfs(node2, 2);
for (auto &c : C) {
if ((int)adj[c].size() == 1) continue;
int64_t res = max(dist[1][c], dist[2][c]);
if (MIN > res) MIN = res, ans = c;
}
far[ans] = MIN;
return ans;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for (int i = 0; i < M; i++)
adj[A[i]].push_back({B[i], T[i]}), adj[B[i]].push_back({A[i], T[i]});
priority_queue<array<int64_t, 2>> pq;
for (int i = 0; i < N; i++)
if (!vis[i]) {
component.clear(), cdfs(i);
int root = fun(component, N); pq.push({far[root], root});
}
while ((int)pq.size() > 1) {
int U = pq.top()[1]; pq.pop();
int V = pq.top()[1]; pq.pop();
if (far[U] == far[V]) {
pq.push({far[V] + L, U}), far[U] = far[V] + L, adj[U].push_back({V, L}), adj[V].push_back({U, L});
continue;
}
adj[U].push_back({V, L}), adj[V].push_back({U, L});
int64_t pfaru = far[U], pfarv = far[V];
far[U] = max(far[U], pfarv + L), far[V] = max(far[V], pfaru + L);
if (far[U] < far[V]) pq.push({far[U], U});
else pq.push({far[V], V});
}
int64_t MAX = 0, node = 0;
dfs(0, 3);
for (int i = 0; i < N; i++) if (MAX < dist[3][i]) MAX = dist[3][i], node = i;
dfs(node, 4);
MAX = 0;
for (int i = 0; i < N; i++) MAX = max(MAX, dist[4][i]);
return MAX;
}
