#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int N = 1e5 + 5, INF = 1e9 + 5;
int n, m, l, maxdia, ans = INF, dist1[N], dist2[N];
vector<pair<int, int>> tree[N];
vector<int> sets, nodes;
bool vis[N];
pair<int, int> dfs(int v, int p){
nodes.push_back(v);
pair<int, int> mx = {0, v};
for(auto e : tree[v]){
if(e.first != p){
pair<int, int> emx = dfs(e.first, v);
mx = max(mx, {emx.first + e.second, emx.second});
}
}
return mx;
}
void dfs2(int v, int p, int d, int* dist){
dist[v] = d;
for(auto e : tree[v]){
if(e.first != p){
dfs2(e.first, v, d + e.second, dist);
}
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]){
n = N, m = M, l = L;
for(int i = 0; i < m; i++){
tree[A[i]].push_back({B[i], T[i]});
tree[B[i]].push_back({A[i], T[i]});
}
for(int v = 0; v < n; v++){
nodes.clear();
if(!vis[v]){
auto p1 = dfs(v, -1);
int a = p1.second;
auto p2 = dfs(a, -1);
int b = p2.second;
maxdia = max(maxdia, p2.first);
auto p3 = dfs(b, -1);
dfs2(a, -1, 0, dist1);
dfs2(b, -1, 0, dist2);
int mx = INF;
for(auto u : nodes) mx = min(mx, max(dist1[u], dist2[u])), vis[u] = true;
sets.push_back(mx);
}
}
if(sets.size() == 1) return maxdia;
multiset<int> st;
for(auto x : sets) st.insert(x);
for(auto x : sets){
st.erase(st.find(x));
int curans = 0;
if(st.size() == 0) curans = INF;
if(st.size() >= 1) curans = max(curans, x + *prev(st.end()) + l);
if(st.size() >= 2) curans = max(curans, *prev(st.end()) + *prev(prev(st.end())) + 2 * l);
ans = min(ans, curans);
st.insert(x);
}
return max(ans, maxdia);
}
