#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, ll>;
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
// Build adjacency list with existing trails
vector<vector<pii>> adj(N);
for (int i = 0; i < M; i++) {
adj[A[i]].push_back({B[i], (ll)T[i]});
adj[B[i]].push_back({A[i], (ll)T[i]}); // Undirected graph
}
// Find connected components and their diameters
vector<ll> group_ans, diameters;
vector<bool> visited(N, false);
for (int i = 0; i < N; i++) {
if (visited[i]) continue;
vector<int> group;
queue<int> qq;
qq.push(i);
visited[i] = true;
while (!qq.empty()) {
int u = qq.front(); qq.pop();
group.push_back(u);
for (auto [v, w] : adj[u]) {
if (!visited[v]) {
visited[v] = true;
qq.push(v);
}
}
}
// Function to find the minimum maximum distance in a component
auto f = [&](const vector<int>& comp) {
if (comp.empty()) return 0LL;
int start = comp[0];
// Find farthest node a from start
vector<bool> vis(N, false);
ll mx_dist = 0;
int a = -1;
queue<pair<int, ll>> q;
q.push({start, 0LL});
while (!q.empty()) {
auto [u, d] = q.front(); q.pop();
if (vis[u]) continue;
vis[u] = true;
if (d > mx_dist) {
mx_dist = d;
a = u;
}
for (auto [v, w] : adj[u]) {
if (!vis[v]) q.push({v, d + w});
}
}
// From a, compute d1 and find b
vector<ll> d1(N, -1LL);
vector<bool> vis2(N, false);
queue<pair<int, ll>> q2;
q2.push({a, 0LL});
ll mx2 = 0;
int b = -1;
while (!q2.empty()) {
auto [u, d] = q2.front(); q2.pop();
if (vis2[u]) continue;
vis2[u] = true;
d1[u] = d;
if (d > mx2) {
mx2 = d;
b = u;
}
for (auto [v, w] : adj[u]) {
if (!vis2[v]) q2.push({v, d + w});
}
}
// From b, compute d2
vector<ll> d2(N, -1LL);
vector<bool> vis3(N, false);
queue<pair<int, ll>> q3;
q3.push({b, 0LL});
while (!q3.empty()) {
auto [u, d] = q3.front(); q3.pop();
if (vis3[u]) continue;
vis3[u] = true;
d2[u] = d;
for (auto [v, w] : adj[u]) {
if (!vis3[v]) q3.push({v, d + w});
}
}
diameters.push_back(d1[b]);
ll ans = LLONG_MAX;
for (int i : comp) {
if (d1[i] != -1 && d2[i] != -1) {
ans = min(ans, max(d1[i], d2[i]));
}
}
return ans;
};
group_ans.push_back(f(group));
}
// Sort diameters in descending order
sort(group_ans.rbegin(), group_ans.rend());
ll res = 0;
size_t k = group_ans.size();
if (k >= 1) res = max(res, group_ans[0]);
if (k >= 2) res = max(res, group_ans[0] + group_ans[1] + L); // L is the new trail length
if (k >= 3) res = max(res, group_ans[1] + group_ans[2] + 2 * L);
for (auto d : diameters) {
res = max(res, d);
}
// Ensure the result fits in int (problem constraints guarantee this)
return (int)min(res, (ll)INT_MAX);
}
