#include "dreaming.h"
#include "bits/stdc++.h"
using namespace std;
const int MAXN = 100005;
vector<pair<int, int>> adj[MAXN];
int dist_A[MAXN], dist_B[MAXN], dist_tmp[MAXN];
bool vis[MAXN];
vector<int> nodes;
void dfs(int u, int p, int d, int* dist_arr) {
dist_arr[u] = d;
vis[u] = true;
nodes.push_back(u);
for (auto &edge : adj[u]) {
if (edge.first != p) {
dfs(edge.first, u, d + edge.second, dist_arr);
}
}
}
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]});
}
vector<int> radii;
int max_diameter = 0;
for (int i = 0; i < N; i++) {
if (!vis[i]) {
nodes.clear();
dfs(i, -1, 0, dist_tmp);
int start_node = i;
for (int x : nodes) if (dist_tmp[x] > dist_tmp[start_node]) start_node = x;
nodes.clear();
dfs(start_node, -1, 0, dist_A);
int end_node = start_node;
for (int x : nodes) if (dist_A[x] > dist_A[end_node]) end_node = x;
int component_diameter = dist_A[end_node];
max_diameter = max(max_diameter, component_diameter);
nodes.clear();
dfs(end_node, -1, 0, dist_B);
int min_max_dist = 2e9 + 7;
for (int x : nodes) {
min_max_dist = min(min_max_dist, max(dist_A[x], dist_B[x]));
}
radii.push_back(min_max_dist);
for (int x : nodes) vis[x] = true;
}
}
sort(radii.rbegin(), radii.rend());
long long res = max_diameter;
if (radii.size() >= 2) {
res = max(res, (long long)radii[0] + radii[1] + L);
}
if (radii.size() >= 3) {
res = max(res, (long long)radii[1] + radii[2] + 2LL * L);
}
return (int)res;
}
