#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
using ll = long long;
using PI = pair<int,int>;
using PLI = pair<int,ll>;
int travelTime(int n, int m, int L, int A[], int B[], int T[]) {
vector<vector<PI>> g(n);
for (int i = 0; i < m; ++i) {
g[A[i]].push_back({B[i], T[i]});
g[B[i]].push_back({A[i], T[i]});
}
vector<char> seen(n, 0);
vector<ll> radii; // radius for each component
ll globalMaxDiameter = 0;
auto farthest_and_dist = [&](int start, const vector<int>& comp_nodes) {
// iterative stack DFS to compute dist from start to all nodes in this component
vector<ll> dist(n, -1);
vector<int> st;
st.reserve(comp_nodes.size());
st.push_back(start);
dist[start] = 0;
for (size_t idx = 0; idx < st.size(); ++idx) {
int u = st[idx];
for (auto [v, w] : g[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + (ll)w;
st.push_back(v);
}
}
}
// find farthest among comp_nodes
int far = start;
ll farD = 0;
for (int u : comp_nodes) {
if (dist[u] > farD) { farD = dist[u]; far = u; }
}
return tuple<int,ll,vector<ll>>(far, farD, move(dist));
};
// find connected components
for (int i = 0; i < n; ++i) {
if (seen[i]) continue;
// collect component nodes via iterative DFS
vector<int> comp;
stack<int> st; st.push(i); seen[i] = 1;
while (!st.empty()) {
int u = st.top(); st.pop();
comp.push_back(u);
for (auto [v, w] : g[u]) if (!seen[v]) { seen[v] = 1; st.push(v); }
}
// if single-node component
if (comp.size() == 1) {
radii.push_back(0);
globalMaxDiameter = max(globalMaxDiameter, 0LL);
continue;
}
// 1) find one diameter endpoint A
auto [Aend, d1, distA] = farthest_and_dist(comp[0], comp);
// 2) from Aend find Bend and distances distFromAend (already got distA if start==Aend)
auto [Bend, diameter, distFromA] = farthest_and_dist(Aend, comp);
globalMaxDiameter = max(globalMaxDiameter, diameter);
// 3) from Bend distances
int tmpStart = Bend;
auto [_, dtmp, distFromB] = farthest_and_dist(tmpStart, comp);
// 4) component radius = min over nodes of max(distFromA[node], distFromB[node])
ll radius = (ll)4e18;
for (int u : comp) {
ll mx = max(distFromA[u], distFromB[u]);
if (mx < radius) radius = mx;
}
radii.push_back(radius);
}
// if only one component
int k = (int)radii.size();
if (k == 1) return (int)globalMaxDiameter;
sort(radii.begin(), radii.end(), greater<ll>()); // r1 >= r2 >= ...
ll ans = globalMaxDiameter;
// connect two largest
ans = max(ans, radii[0] + radii[1] + L);
if (k >= 3) ans = max(ans, radii[1] + radii[2] + 2LL * L);
return (int)ans;
}
