#include <bits/stdc++.h>
#include <dreaming.h>
using namespace std;
// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")
#define mp make_pair
#define fi first
#define se second
#define all(v) v.begin(),v.end()
#define allarr(a) a , a + n
#define ll long long
#define pb push_back
#define fastio ios_base::sync_with_stdio(false) ; cin.tie(NULL); cout.tie(NULL)
typedef pair<int, int> pi;
typedef pair<ll,ll> pll ;
typedef pair<int,pi> trp ;
typedef vector<pi> vpi;
typedef priority_queue< int, vector <int> , greater<int> > spq;
const int NN = 1e5+5 ;
vector<pll> adj[NN] ;
ll dp1[NN],dp2 [NN] , chil[NN] , chil1[NN], pass[NN] ,ans , ans1 ;
void dfs0(int u , int p ){
pass[u]=1;
int v ; ll w ;
// cout << "dfs0"<<endl;
for(pi pr : adj[u]){
v = pr.fi ;
w = pr.se ;
if( p != v ){
dfs0(v,u) ;
if( dp1[v] + w > dp1[u]){
dp1[u] = dp1[v] + w ;
chil[u] = v ;
}
}
}
}
void dfs1(int u , int p ){
int v ; ll w ;
pass[u]=2;
// cout << "dfs1"<<endl;
for(pi pr : adj[u]){
v = pr.fi ;
w = pr.se ;
if(p!=v)
dfs1(v,u);
if( p != v && v != chil[u] ){
if( dp1[v]+w > dp2[u] ){
chil1[u] = v ;
dp2[u] = dp1[v]+w ;
}
}
}
}
void dfs2(int u , int p ){
int v ; ll w ;
pass[u]=3;
// cout << "dfs2"<<endl;
for(pi pr : adj[u]){
v = pr.fi ;
w = pr.se ;
if( v != p && v != chil[u] ){
if( dp1[u] + w > dp1[v] ){
dp2[v] = dp1[v] ;
chil1[v] = chil[v] ;
dp1[v] = dp1[u] + w;
chil[v] = u ;
}else if( dp1[u] + w > dp2[v]){
dp2[v] = dp1[u] + w;
chil1[v] = u ;
}
}else if( v != p && v != chil1[u]){
if( dp2[u] + w > dp1[v] ){
dp2[v] = dp1[v] ;
dp1[v] = dp2[u] + w;
chil1[v] = chil[v] ;
chil[v] = u ;
}else if( dp2[u] + w > dp2[v]){
dp2[v] = dp2[u] + w;
chil1[v] = u ;
}
}
if( v!= p )
dfs2(v,u) ;
}
}
void dfs4(int u , int p , ll& Min ){
pass[u]=4;
Min = min(Min,dp1[u]);
ans1 = max(ans1,dp1[u]);
for(pi v : adj[u]){
if(v.fi!=p){
dfs4(v.fi,u,Min);
}
}
}
void edge(int u , int v , int w ){
adj[u].pb({v,1LL*w}) ;
}
int travelTime(int N,int M,int L ,int A[],int B[],int T[]){
// cout <<"x"<<endl;
for(int i = 0 ; i < M ; i++ ){
edge(A[i],B[i],T[i]) ;
edge(B[i],A[i],T[i]) ;
}
for(int i = 0 ; i < N ; i++ )if( pass[i] == 0 ) dfs0(i,-1) ;
for(int i = 0 ; i < N ; i++ )if( pass[i] == 1 ) dfs1(i,-1) ;
for(int i = 0 ; i < N ; i++ )if( pass[i] == 2 ) dfs2(i,-1) ;
ll Min ;
vector<ll> longest_paths;
for(int i = 0 ; i < N ; i++ ){
Min = 1e18;
if( pass[i] == 3 ){
dfs4(i,-1,Min);
longest_paths.pb(Min);
}
}
sort(all(longest_paths));
reverse(all(longest_paths)) ;
ans = 0;
// if( N == 2 )return L ;
// if( N == 1 )
// cout << "L "<< L << endl;
// for(int p : longest_paths)cout << p << " ";
if( longest_paths.size() > 1 ){
ans = max(ans,L+longest_paths[0]+longest_paths[1]);
if( longest_paths.size() > 2 ){
ans = max(ans,2*L+longest_paths[1]+longest_paths[2]);
}
}
ans = max (ans,ans1);
// if( ans == 631 )return L;
return ans ;
}
// int main(){
// int n , m , l ;
// cin >> n >> m >> l ;
// int a[n+1] , b[n+1] , t[n+1] ;
// for(int i = 0 ; i < n ;i++ )cin >> a[i]>>b[i]>>t[i] ;
// cout << travelTime(n,m,l,a,b,t) << endl;
// }
