#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int N = 1e5;
const int inf = 2e9;
vector<pair<int,int>> adj[N];
int down[N],up[N];
bool vis[N];
void dfs(int u){
vis[u] = true;
vector<pair<int,int>> all;
for(auto [v,w] : adj[u]){
if(vis[v]) continue;
dfs(v);
all.emplace_back(v,w);
}
int maxi = -inf;
for(auto [v,w] : all){
up[v] = max(up[v],maxi + w);
maxi = max(maxi,down[v] + w);
}
reverse(all.begin(),all.end());
maxi = -inf;
for(auto [v,w] : all){
up[v] = max(up[v],maxi + w);
maxi = max(maxi,down[v] + w);
down[u] = maxi;
}
}
int mini = inf;
void dfs2(int u,int p){
for(auto[v,w] : adj[u]){
if(v == p) continue;
up[v] = max(up[v],up[u] + w);
dfs2(v,u);
}
mini = min(mini,max(down[u],up[u]));
}
int travelTime(int N,int M,int L,int A[],int B[],int T[]){
for(int i = 0;i<N;i++){
up[i] = down[i] = 0;
vis[i] = false;
}
for(int i = 0;i<M;i++){
adj[A[i]].emplace_back(B[i],T[i]);
adj[B[i]].emplace_back(A[i],T[i]);
}
vector<int> arr;
int ans = 0;
int cc = 0;
for(int i = 0;i<N;i++){
if(!vis[i]){
mini = inf;
dfs(i);
dfs2(i,-1);
arr.push_back(mini);
cc ++;
}
ans = max(ans,up[i]);
}
assert(cc - 1 == N - M - 1);
sort(arr.begin(),arr.end());
int tot = inf;
if(arr.size() == 1){
return ans;
}
if(arr.size() == 2){
return max(ans,arr[0] + arr[1] + L);
}else if(arr.size() > 2){
int a = arr[arr.size() - 3];
int b = arr[arr.size() - 2];
int c = arr[arr.size() - 1];
tot = min(tot,max(b + c + L,a + c + 2 * L));
tot = min(tot,max(b + c + L,a + b + 2 * L));
}
return max(tot,ans);
}
