#include<bits/stdc++.h>
#include"dreaming.h"
#define f first
#define s second
using namespace std;
const int N = 2e5 + 500;
typedef pair<int, int> ipair;
int n , m , L;
vector<ipair> adj[N];
int dpD[N] , dpU[N];
bool vis[N];
vector<int> dist;
int MN = 2e9 + 5;
int mx1 = -1 , mx2 = -1;
void dfsU(int u , int p , int BOSS){
for(ipair x : adj[u]){
int v = x.f , w = x.s;
if(v == p) continue;
if(u == BOSS){
if(dpD[v] + w == mx1){
if(mx2 == -1) dpU[v] = w;
else dpU[v] = mx2 + w;
} else dpU[v] = mx1 + w;
}
else dpU[v] = dpU[u] + w;
dfsU(v , u , BOSS);
}
MN = min(MN , max(dpU[u] , dpD[u]));
}
void dfsD(int u , int BOSS){
vis[u] = 1;
for(ipair x : adj[u]){
int v = x.f , w = x.s;
if(vis[v]) continue;
dfsD(v , BOSS);
dpD[u] = max(dpD[u] , dpD[v] + w);
if(u == BOSS){
if(mx2 < dpD[v] + w){mx2 = dpD[v] + w; if(mx2 > mx1) swap(mx1 , mx2);}
}
}
if(u == BOSS){ dfsU(u ,-1 , BOSS);}
}
int travelTime(int N , int M , int L , int A[] , int B[] , int C[]){
n = N; m = M; L = L;
for(int i = 0; i < m; ++i){
adj[A[i]].emplace_back(B[i] , C[i]);
adj[B[i]].emplace_back(A[i] , C[i]);
}
for(int i = 0; i < n; ++i){
if(!vis[i]) {
dfsD(i , i);
dist.emplace_back(MN);
//cerr << MN << " mn " << endl;
MN = 2e9; mx1 = -1; mx2 = -1;
}
}
sort(dist.begin() , dist.end()); reverse(dist.begin() ,dist.end());
return max(dist[0] + dist[1] + L , dist[1] + dist[2] + L + L);
}
/*
int main (){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m >> L;
for(int i = 0; i < m; ++i){
int u , v , w;
cin >> u >> v >> w;
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
for(int i = 0; i < n; ++i){
if(!vis[i]) {
dfsD(i , i);
dist.emplace_back(MN);
//cerr << MN << " mn " << endl;
MN = 2e9; mx1 = -1; mx2 = -1;
}
}
sort(dist.begin() , dist.end()); reverse(dist.begin() ,dist.end());
cout << max(dist[0] + dist[1] + L , dist[1] + dist[2] + L + L);
}
*/
