#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<array<int, 2>>> adj;
vector<int> dist, nodes;
int n;
array<int, 2> bfs (int u, bool f) {
queue<array<int, 3>> q {{{u, 0, -1}}};
array<int, 2> MX {0, u};
int v = 0;
while (q.size()) {
++v;
u = q.front()[0];
int d = q.front()[1];
int p = q.front()[2];
q.pop();
if (f) {
nodes.push_back(u);
dist[u] = max(dist[u], d);
}
MX = max(MX, {d, u});
for (auto &v : adj[u]) {
if (v[0] != p) {
q.push({v[0], d + v[1], u});
}
}
}
return MX;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n = N;
adj.resize(N);
dist.resize(N);
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]});
}
vector<array<int, 2>> cmp;
for (int i = 0; i < N; ++i) {
if (!dist[i]) {
int a = bfs(i, 0)[1];
nodes.clear();
bfs(bfs(a, 1)[1], 1);
array<int, 2> mn = {(int)2e9, (int)2e9};
for (int u : nodes) {
mn = min(mn, {dist[u], u});
}
cmp.push_back(mn);
}
}
int mx = (*max_element(cmp.begin(), cmp.end()))[1];
for (auto &e : cmp) {
if (e[1] != mx) {
adj[e[1]].push_back({mx, L});
adj[mx].push_back({e[1], L});
}
}
return bfs(bfs(0, 0)[1], 0)[0];
}
