#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] , dpD1[N] , dpD2[N];
bool vis[N];
vector<int> dist;
int ans;
int MN = 2e9 + 5;
void dfsU(int u , int p){
for(ipair x : adj[u]){
int v = x.f , w = x.s;
if(v == p) continue;
dpU[v] = dpU[u] + w;
if(dpD[v] + w == dpD1[u]){
if(dpD2[u] != -1) dpU[v] = max(dpU[v] , dpD2[u] + w);
} else dpU[v] = max(dpU[v] , dpD1[u] + w);
dfsU(v , u);
}
MN = min(MN , max(dpD[u] , dpU[u]));
ans = max(ans , dpD[u] + dpU[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(dpD2[u] < dpD[v] + w){dpD2[u] = dpD[v] + w; if(dpD2[u] > dpD1[u])swap(dpD2[u] , dpD1[u]);};
}
if(u == BOSS) dfsU(u ,-1);
}
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]);
}
memset(dpD1 , -1 , sizeof(dpD1));
memset(dpD2 , -1 , sizeof(dpD2));
for(int i = 0; i < n; ++i){
if(!vis[i]){
dfsD(i , i);
dist.emplace_back(MN);
//cerr << MN << " mn " << endl;
MN = 2e9;
}
}
/*
for(int i = 0; i < n; ++i){
cerr << i << " i " << dpD[i] << " dpD " << dpU[i] << " dpU " << endl;
}*/
sort(dist.begin() , dist.end()); reverse(dist.begin() ,dist.end());
//for(int i = 0; i < dist.size(); ++i) cerr << dist[i] << " "; cerr << endl;
if(dist.size() >= 2) ans = max(ans , dist[0] + dist[1] + L);
if(dist.size() >= 3) ans = max(ans , dist[1] + dist[2] + 2 * L);
return ans;
//cerr << ans << "ans" << endl;
}
