#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 4e18;
static vector<vector<pair<int,ll>>> adj;
pair<int,ll> farthest(int start, vector<ll>& dist, const vector<int>& comp) {
// BFS/DFS works too since each comp is a tree, but Dijkstra is safe
unordered_set<int> inComp(comp.begin(), comp.end());
dist.assign(adj.size(), INF);
priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
dist[start] = 0;
pq.push({0,start});
while(!pq.empty()) {
auto [d,u] = pq.top(); pq.pop();
if(d != dist[u]) continue;
for(auto [v,w]: adj[u]) {
if(!inComp.count(v)) continue;
if(dist[v] > d + w) {
dist[v] = d + w;
pq.push({dist[v], v});
}
}
}
int bestNode = start;
ll bestDist = -1;
for(int v: comp) {
if(dist[v] < INF && dist[v] > bestDist) {
bestDist = dist[v];
bestNode = v;
}
}
return {bestNode, bestDist};
}
long long travelTime(int N, int M, int L,
int A[], int B[], int T[]) {
adj.assign(N, {});
for(int i=0;i<M;i++){
int u = A[i], v = B[i];
ll w = T[i];
adj[u].push_back({v,w});
adj[v].push_back({u,w});
}
vector<int> seen(N,0);
vector<ll> radii;
ll maxDiam = 0;
vector<ll> distA, distB;
for(int i=0;i<N;i++) if(!seen[i]){
// collect component
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,_]: adj[u]) if(!seen[v]){ seen[v]=1; st.push(v);}
}
// diameter endpoints
auto [a,_1] = farthest(comp[0], distA, comp);
auto [b,diam] = farthest(a, distA, comp);
maxDiam = max(maxDiam, diam);
// compute radius
farthest(a, distA, comp);
farthest(b, distB, comp);
ll radius = INF;
for(int v: comp){
radius = min(radius, max(distA[v], distB[v]));
}
radii.push_back(radius);
}
sort(radii.begin(), radii.end(), greater<ll>());
ll ans = maxDiam;
if(radii.size() == 1){
// nothing
} else if(radii.size() == 2){
ans = max(ans, radii[0] + radii[1] + L);
} else {
ans = max(ans, radii[0] + radii[1] + L);
ans = max(ans, radii[1] + radii[2] + 2*L);
}
return ans;
}
