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