#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)
unordered_map<int, vector<pair<int, int>>> adjList;
bool vis[100005];
int d1[100005];
int d2[100005];
void dp1(vector<int> &comp, vector<int> &leaves, int v, int p = -1) {
comp.push_back(v);
d1[v] = 0;
int mxp1 = -1, mxp2 = -1;
for(auto i : adjList[v]) if(i.first != p) {
dp1(comp, leaves, i.first, v);
int pl = d1[i.first] + i.second;
d1[v] = max(d1[v], pl);
if(mxp1 < pl) {
mxp2 = mxp1;
mxp1 = pl;
} else if (mxp2 < pl) mxp2 = pl;
}
if(mxp2 != -1) {
d2[v] = mxp1+mxp2;
}
if(mxp1 != -1) leaves.push_back(v);
}
pair<int, int> solve(int r) {
vector<int> connComp;
vector<int> leaves;
dp1(connComp, leaves, r);
priority_queue<pair<int, int>, vector<pair<int, int>>> pq;
for(auto i : leaves) {pq.emplace(make_pair(0, i)); vis[i] = true;}
int rad = 0;
while(!pq.empty()) {
pair<int, int> top = pq.top(); pq.pop();
rad = top.first;
if(vis[top.second]) continue;
for(auto i : adjList[top.second]) {
if(!vis[i.first]) {
pq.emplace(make_pair(i.second + top.first, i.first));
}
}
vis[top.second] = true;
}
int d = 0;
for(auto i : connComp) d = max(d, max(d1[i], d2[i]));
return make_pair(d, rad);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
memset(vis, false, sizeof(vis));
memset(d1, -1, sizeof(vis));
memset(d2, -1, sizeof(vis));
for(int i = 0; i < M; i++) {
adjList[A[i]].push_back({B[i], T[i]});
adjList[B[i]].push_back({A[i], T[i]});
}
vector<int> radii;
vector<int> diams;
int comps = 0;
for(int i = 0; i < N; i++) {
if(!vis[i]) {
pair<int, int> ans = solve(i);
diams.push_back(ans.first);
radii.push_back(ans.second);
comps++;
}
}
sort(radii.begin(), radii.end());
sort(diams.begin(), diams.end());
if(comps == 1) {
return diams[0];
} else if (comps == 2) {
return min(max(diams[0], diams[1]), radii[0] + radii[1] + L);
} else {
return min({max(diams[0], diams[1]), radii[0] + radii[1] + L, radii[1] + radii[2] + L + L});
}
}
