#include "dreaming.h"
#include "bits/stdc++.h"
using namespace std;
const int64_t MXN = 1e3 + 5;
vector<array<int64_t, 2>> adj[MXN];
vector<int64_t> comp;
int64_t dist[MXN], far[MXN];
bool vis[MXN];
void findcomp(const int64_t &node) {
comp.push_back(node), vis[node] = true;
for (auto &[child, cost] : adj[node]) if (!vis[child]) findcomp(child);
}
void dfs(const int64_t &node, int64_t par = 0) {
for (auto &[child, cost] : adj[node]) if (child != par) dist[child] = dist[node] + cost, dfs(child, node);
}
array<int64_t, 2> longest_dist(const int64_t &node, const int64_t &n) {
memset(dist, 0x3f, sizeof(dist)); dist[node] = 0;
dfs(node);
int64_t MAX = 0, res = 0;
for (int64_t i = 0; i < n; i++) if (MAX < dist[i]) MAX = dist[i], res = i;
return {res, MAX};
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for (int64_t 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 (int64_t i = 0; i < N; i++)
if (!vis[i]) {
comp.clear(), findcomp(i);
int64_t root = i, MIN = INT64_MAX;
for (auto &c : comp) {
memset(dist, 0x3f, sizeof(dist)); dist[c] = 0;
int64_t MAX = 0; dfs(c);
for (auto &r : comp) MAX = max(MAX, dist[r]);
far[c] = MAX;
if (far[c] < MIN) MIN = far[c], root = c;
}
pq.push({far[root], root});
}
int64_t root = pq.top()[1]; pq.pop();
while (!pq.empty()) {
int64_t node = pq.top()[1]; pq.pop();
adj[node].push_back({root, L}), adj[root].push_back({node, L});
}
array<int64_t, 2> X = longest_dist(0, N);
array<int64_t, 2> Y = longest_dist(X[0], N);
return Y[1];
}
