#include <bits/stdc++.h>
#include <dreaming.h>
using namespace std;
typedef int ll;
const int N = 1e5 + 11;
int ans = 1e9, res = 0;
ll x, y;
ll d[N], d1[N], d2[N], was[N], par[N];
vector < pair < ll, ll > > g[N];
void dfs(ll v, ll p){
was[v] = 1;
if(x == -1 || d[v] > d[x]) x = v;
for(auto [u, w] : g[v])
if(u != p)
par[u] = v, d[u] = d[v] + w, dfs(u, v);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(ll i = 0; i < N; i++) par[i] = -1;
for(ll i = 0; i < M; i++) g[A[i]].push_back({B[i], T[i]});
for(ll i = 0; i < M; i++) g[B[i]].push_back({A[i], T[i]});
if(N - 1 == M) return 0;
vector < ll > vec;
multiset < ll > st;
for(ll i = 0, v1, v2, dd; i < N; i++){
if(!was[i]){
x = -1, d[i] = 0, dfs(i, i), v1 = x;
x = -1, d[v1] = 0, dfs(v1, v1), v2 = x;
dd = d[v2], res = max(res, d[v2]);
while(1){
if(v1 == v2 || max(d[v2], dd - d[v2]) <= max(d[par[v2]], dd - d[par[v2]])) break;
v2 = par[v2];
}
vec.push_back(max(d[v2], dd - d[v2]));
st.insert(max(d[v2], dd - d[v2]));
}
}
for(ll val : vec){
st.erase(st.find(val));
int it = val + L + *st.rbegin(), jt = 0;
if(st.size() > 1) jt = *st.rbegin() + *(--st.rbegin()) + 2 * L;
ans = min(ans, max(it, jt));
st.insert(val);
}
return max(ans, res);
}
