#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std ;
#define pii pair <int , int>
#define ff first
#define ss second
const int inf = 1e9 ;
const int N = 1e5 + 5 ;
template <class T>
bool chmax( T& x , const T& y ){
bool f = 0 ;
if ( x < y ) x = y , f = 1 ;
return f ;
}
template <class T>
bool chmin( T &x , const T &y ){
bool f = 0 ;
if ( x > y ) x = y , f = 1 ;
return f ;
}
bool vis[N] ;
int d[N] , f[N] , sc[N] ;
int mx , m , r ;
pii ans[N] ;
vector <pii> g[N] ;
vector <pii> vec ;
void dfs ( int v , int s , int& m ){
vis[v] = 1 ; d[v] = s ;
if ( mx <= d[v] ){
m = v ; mx = d[v] ;
}
for ( auto to : g[v] ) if ( !vis[to.ff] ) dfs(to.ff,s+to.ss,m) ;
}
void fir ( int v , int d , int& m ){
vis[v] = 0 ; f[v] = d ;
if ( chmax ( mx , f[v] ) ) m = v ;
for ( auto to : g[v] ) if ( vis[to.ff] ) fir(to.ff,d+to.ss,m) ;
}
void sec ( int v , int d , int& m ){
vis[v] = 1 ; sc[v] = d ;
if ( max( f[v] , sc[v] ) < mx ){
mx = max ( f[v] , sc[v] ) ; m = v ;
}
for ( auto to : g[v] ) if ( !vis[to.ff] ) sec(to.ff,d+to.ss,m) ;
}
int travelTime(int n, int m, int l, int a[], int b[], int c[]) {
vec.clear() ; r = 0 ;
for ( int i = 0 ; i < m ; i ++ ){
g[a[i]].push_back({b[i],c[i]}) ;
g[b[i]].push_back({a[i],c[i]}) ;
}
for ( int i = 0 ; i <= n ; i ++ ){
if ( !vis[i] ){
mx = 0 ;
dfs(i,0,m) ;
mx = 0 ;
fir(m,0,m) ;
chmax ( r , f[m] ) ;
mx = inf ;
sec(m,0,m) ;
vec.push_back({max(f[m],sc[m]),m}) ;
}
}
if ( n == 1 ) return 0 ;
if ( n == 2 ){
if ( m == 1 ) return 0 ;
return l ;
} int ans = r ;
sort ( vec.rbegin() , vec.rend() ) ;
if ( vec.size() > 1 ) chmax ( ans , l+vec[0].ff + vec[1].ff ) ;
if ( vec.size() > 2 ) chmax ( ans , 2*l+vec[1].ff + vec[2].ff ) ;
return ans ;
}
/*
signed main(){
int n , m , l , a[N] , b[N] , t[N] ;
cin >> n >> m >> l ;
for ( int i = 0 ; i < m ; i ++ ) cin >> a[i] >> b[i] >> t[i] ;
cout << travelTime( n , m , l , a , b , t ) ;
}
*/
