#include <bits/stdc++.h>
#if __has_include("dreaming.h")
#include "dreaming.h"
#endif
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,tune=native")
using namespace std;
using ll = long long;
#ifdef LOCAL
#include "debug.h"
#else
#define dbg(...) 0
#define dbgn(...) 0
#endif
const int INF = 1e9;
// Assuming the function signature from the problem
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
vector<vector<pair<int, int>>> adj(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]});
}
const int INF = 1e9;
vector<int> cc_radii;
vector<int> cc_diameters;
auto dijkstra = [&](int start_node) {
vector<int> dist(n, INF);
if (start_node >= 0 && start_node < n) {
dist[start_node] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, start_node});
while (!pq.empty()) {
int d = pq.top().first;
int u = pq.top().second;
pq.pop();
if (d > dist[u]) continue;
for (auto& edge : adj[u]) {
int v = edge.first;
int weight = edge.second;
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.push({dist[v], v});
}
}
}
}
return dist;
};
vector<bool> vis(n, false);
for (int i = 0; i < n; ++i) {
if (!vis[i]) {
vector<int> ccn;
queue<int> q;
q.push(i);
vis[i] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
ccn.push_back(u);
for (auto& edge : adj[u]) {
int v = edge.first;
if (!vis[v]) {
vis[v] = true;
q.push(v);
}
}
}
if (ccn.size() <= 1) {
cc_radii.push_back(0);
cc_diameters.push_back(0);
continue;
}
vector<int> st_dist = dijkstra(i);
int endpoint_a = -1;
int max_dist = -1;
for (int node : ccn) {
if (st_dist[node] != INF && st_dist[node] > max_dist) {
max_dist = st_dist[node];
endpoint_a = node;
}
}
vector<int> a_dist = dijkstra(endpoint_a);
int endpoint_b = -1;
int component_diameter = -1;
for (int node : ccn) {
if (a_dist[node] != INF && a_dist[node] > component_diameter) {
component_diameter = a_dist[node];
endpoint_b = node;
}
}
cc_diameters.push_back(component_diameter);
vector<int> b_dist = dijkstra(endpoint_b);
int component_radius = INF;
for (int node : ccn) {
int e = max(a_dist[node], b_dist[node]);
if (e < component_radius) {
component_radius = e;
}
}
cc_radii.push_back(component_radius);
}
}
int ans = 0;
if (!cc_diameters.empty()) {
ans = *max_element(cc_diameters.begin(), cc_diameters.end());
}
sort(cc_radii.begin(), cc_radii.end(), greater<int>());
if (cc_radii.size() >= 2) {
ans = max(ans, cc_radii[0] + cc_radii[1] + l);
}
if (cc_radii.size() >= 3) {
ans = max(ans, cc_radii[1] + cc_radii[2] + 2 * l);
}
return ans;
}
