#include "dreaming.h"
#include "bits/stdc++.h"
using namespace std;
const int MAXN = 100005;
vector<pair<int, int>> adj[MAXN];
int dist[MAXN], parent[MAXN], edge_weight[MAXN];
bool vis[MAXN];
vector<int> current_comp;
pair<int, int> bfs(int start) {
queue<int> q;
q.push(start);
dist[start] = 0;
parent[start] = -1;
vis[start] = true;
current_comp.clear();
current_comp.push_back(start);
int farthest_node = start;
while(!q.empty()){
int u = q.front(); q.pop();
if(dist[u] > dist[farthest_node]) farthest_node = u;
for(auto &edge : adj[u]){
int v = edge.first;
if(!vis[v]){
vis[v] = true;
dist[v] = dist[u] + edge.second;
parent[v] = u;
edge_weight[v] = edge.second;
q.push(v);
current_comp.push_back(v);
}
}
}
for(int node : current_comp) vis[node] = false;
return {farthest_node, dist[farthest_node]};
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
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]});
}
vector<int> radii;
int max_diam = 0;
vector<bool> global_vis(N, false);
for (int i = 0; i < N; i++) {
if (!global_vis[i]) {
pair<int, int> p1 = bfs(i);
pair<int, int> p2 = bfs(p1.first);
max_diam = max(max_diam, p2.second);
for(int node : current_comp) global_vis[node] = true;
int curr = p2.first;
int total_dist = p2.second;
int best_r = total_dist;
int dist_from_end = 0;
while(curr != -1) {
best_r = min(best_r, max(dist_from_end, total_dist - dist_from_end));
dist_from_end += edge_weight[curr];
curr = parent[curr];
}
radii.push_back(best_r);
}
}
sort(radii.rbegin(), radii.rend());
long long res = max_diam;
if (radii.size() >= 2) res = max(res, (long long)radii[0] + radii[1] + L);
if (radii.size() >= 3) res = max(res, (long long)radii[1] + radii[2] + 2LL * L);
return (int)res;
}
