# include "dreaming.h"
# include <iostream>
# include <vector>
# include <algorithm>
using namespace std;
const int NN = 1e5 + 100;
vector < pair < int, long long > > gr[NN];
vector < pair < long long, long long > > rads;
long long dist1[NN], dist2[NN], dia, rad, u;
bool used[NN];
void dfs( int v, int f, int c )
{
used[v] = true;
for ( auto to: gr[v] ){
if( to.first == f )
continue;
else{
long long dst = 0;
if( c == 1 ){
dist1[to.first] = dist1[v] + to.second;
dst = dist1[to.first];
}
else{
dist2[to.first] = dist2[v] + to.second;
dst = dist2[to.first];
}
if( dia < dst ){
dia = dst;
u = to.first;
}
dfs( to.first, v, c );
}
}
}
void jfs( int v, int f )
{
rad = min( rad, max( dist1[v], dist2[v] ) );
for ( auto to: gr[v] ){
if( to.first == f )
continue;
else{
jfs( to.first, v );
}
}
}
pair < long long, long long > get( int v )
{
dia = 0; u = 0;
dist1[v] = 0;
dfs( v, -1, 1 );
if( u == 0 )return {0, 0};
v = u; dia = 0;
dist1[v] = 0;
dfs( v, -1, 1 );
dist2[u] = 0;
dfs( u, -1, 2 );
rad = 1e18;
jfs( v, -1 );
return make_pair( rad, dia );
}
int travelTime( int N, int M, int L, int A[], int B[], int T[] )
{
for ( int i = 0; i < M; i ++ ){
gr[A[i]].push_back( { B[i], T[i] } );
gr[B[i]].push_back( { A[i], T[i] } );
}
for ( int i = 0; i < N; i ++ ){
if( used[i] ) continue;
rads.push_back( get( i ) );
}
sort( rads.begin(), rads.end() );
long long MaxDiameter = 0;
for ( auto rd: rads )
MaxDiameter = max( MaxDiameter, rd.second );
if( rads.size() == 1 )
return rads.back().second;
else if( rads.size() == 2 )
return max( MaxDiameter, rads[0].first + rads[1].first + L);
else
return max( MaxDiameter, max( rads[0].first + rads[1].first + L, rads[1].first + rads[2].first + L + L ) );
}
/*
int main()
{
int n, m, l;
cin >> n >> m >> l;
int a[NN] = {}, b[NN] = {}, t[NN] = {};
for ( int i = 0; i < m; i ++ ){
cin >> a[i] >> b[i] >> t[i];
}
cout << travelTime( n, m, l, a, b, t );
}
*/
