#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Edge{
int to;
int w;
};
static vector<vector<Edge>> g;
static vector<ll> dist_arr;
static vector<int> dist_used;
static pair<int,ll> bfsFarthest(int src, const vector<char>& inComp) {
queue<int> q;
dist_arr[src] = 0;
dist_used.clear();
dist_used.push_back(src);
q.push(src);
int bestNode = src;
ll bestDist = 0;
while (!q.empty()) {
int v = q.front(); q.pop();
ll d = dist_arr[v];
if (d > bestDist) {
bestDist = d;
bestNode = v;
}
for (auto &e : g[v]) {
int u = e.to;
if (!inComp[u]) continue;
if (dist_arr[u] != -1) continue;
dist_arr[u] = d + e.w;
dist_used.push_back(u);
q.push(u);
}
}
return {bestNode, bestDist};
}
static void resetDist() {
for (int v : dist_used) {
dist_arr[v] = -1;
}
dist_used.clear();
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
g.assign(N, {});
for (int i = 0; i < M; i++) {
int a = A[i], b = B[i], w = T[i];
g[a].push_back({b, w});
g[b].push_back({a, w});
}
dist_arr.assign(N, -1);
dist_used.reserve(N);
vector<char> visited(N, 0), inComp(N, 0);
vector<ll> radii;
ll maxDiam = 0;
for (int i = 0; i < N; i++) {
if (visited[i]) continue;
vector<int> nodes;
stack<int> st;
st.push(i);
visited[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 (!visited[u]) {
visited[u] = 1;
st.push(u);
}
}
}
int anyNode = nodes[0];
auto a = bfsFarthest(anyNode, inComp);
int nodeA = a.first;
resetDist();
auto b = bfsFarthest(nodeA, inComp);
int nodeB = b.first;
vector<ll> da;
da.reserve(nodes.size());
for (int v : nodes) {
da.push_back(dist_arr[v]);
}
resetDist();
auto c = bfsFarthest(nodeB, inComp);
ll diam = c.second;
ll radius = LLONG_MAX;
size_t idx = 0;
for (int v : nodes) {
ll db = dist_arr[v];
ll dmax = max(da[idx], db);
if (dmax < radius) radius = dmax;
idx++;
}
resetDist();
for (int v : nodes) {
inComp[v] = 0;
}
radii.push_back(radius);
if (diam > maxDiam) maxDiam = diam;
}
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;
}
