#include "dreaming.h"
#include "bits/stdc++.h"
using namespace std;
const int MXN = 1e5 + 5;
int64_t dist[10][MXN], far[MXN];
vector<array<int64_t, 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) {
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});
}
int64_t root = pq.top()[1]; pq.pop();
while (!pq.empty()) {
auto [d, node] = pq.top(); pq.pop();
adj[node].push_back({root, L}), adj[root].push_back({node, L});
}
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;
}
