#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Edge{ int to, w; };
static pair<int,ll> farthest(int src, const vector<vector<Edge>>& g, const vector<int>& nodes, const vector<char>& inComp, vector<ll>* outDist) {
vector<ll> dist(g.size(), -1);
vector<int> st;
st.reserve(nodes.size());
st.push_back(src);
dist[src] = 0;
vector<int> par(g.size(), -1);
while(!st.empty()){
int v = st.back(); st.pop_back();
for(auto e: g[v]){
int u = e.to;
if(!inComp[u]) continue;
if(u == par[v]) continue;
if(dist[u] != -1) continue;
par[u] = v;
dist[u] = dist[v] + e.w;
st.push_back(u);
}
}
int bestV = src;
ll bestD = 0;
for(int v: nodes){
if(dist[v] > bestD){
bestD = dist[v];
bestV = v;
}
}
if(outDist) *outDist = std::move(dist);
return {bestV, bestD};
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
vector<vector<Edge>> 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> vis(N, 0), inComp(N, 0);
vector<ll> radii;
ll maxDiam = 0;
for(int i=0;i<N;i++) if(!vis[i]){
vector<int> nodes;
stack<int> st;
st.push(i);
vis[i] = 1;
while(!st.empty()){
int v = st.top(); st.pop();
nodes.push_back(v);
inComp[v] = 1;
for(auto e: g[v]){
int u = e.to;
if(!vis[u]){
vis[u] = 1;
st.push(u);
}
}
}
auto a = farthest(nodes[0], g, nodes, inComp, nullptr);
vector<ll> da, db;
auto b = farthest(a.first, g, nodes, inComp, &da);
auto c = farthest(b.first, g, nodes, inComp, &db);
maxDiam = max(maxDiam, c.second);
ll rad = (ll)4e18;
for(int v: nodes) rad = min(rad, max(da[v], db[v]));
radii.push_back(rad);
for(int v: nodes) inComp[v] = 0;
}
sort(radii.begin(), radii.end(), greater<ll>());
ll ans = maxDiam;
if((int)radii.size() >= 2) ans = max(ans, radii[0] + (ll)L + radii[1]);
if((int)radii.size() >= 3) ans = max(ans, radii[1] + 2LL*(ll)L + radii[2]);
return (int)ans;
}
