#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std ;
const int L = 24 ;
const int N = 1e5+5 ;
const int O = 2e9 ;
bool vs[N] ;
vector <int> v , ans ;
vector <pair<int,int>> g[N] ;
pair <int,int> dfs ( int i , int l ) {
vs[i] = 1 ;
pair <int,int> ret = {0,i} ;
for ( auto it : g[i] ) {
if ( it.first != l ) {
pair <int,int> p = dfs ( it.first , i ) ;
p.first += it.second ;
if ( p.first > ret.first ) {
ret = p ;
}
}
}
return ret ;
}
bool path ( int i , int l , int j ) {
if ( i == j ) {
return 1 ;
}
for ( auto it : g[i] ) {
if ( it.first != l ) {
if ( path ( it.first , i , j ) ) {
v.push_back(it.second) ;
return 1 ;
}
}
}
return 0 ;
}
int travelTime(int n, int m, int l, int A[], int B[], int T[]) {
for ( int i = 0 ; i < m ; i++ ) {
g[A[i]+1].push_back({B[i]+1,T[i]}) ;
g[B[i]+1].push_back({A[i]+1,T[i]}) ;
}
int jean = 0 ;
for ( int i = 1 ; i <= n ; i++ ) {
if ( vs[i] ) {
continue ;
}
int a = dfs ( i , 0 ).second ;
int b = dfs ( a , 0 ).second ;
path ( a , 0 , b ) ;
int x = 0 ;
for ( auto it : v ) {
x += it ;
}
jean = max ( jean , x ) ;
int cur = x , sum = 0 ;
for ( auto it : v ) {
sum += it ;
cur = min ( cur , max ( sum , x - sum ) ) ;
}
reverse ( v.begin() , v.end() ) ;
sum = 0 ;
for ( auto it : v ) {
sum += it ;
cur = min ( cur , max ( sum , x - sum ) ) ;
}
ans.push_back(cur) ;
v.clear() ;
}
sort ( ans.begin() , ans.end() , greater <int> () ) ;
if ( ans.size() > 1 ) {
jean = max ( jean , ans[0] + ans[1] + l ) ;
}
if ( ans.size() > 2 ) {
jean = max ( jean , ans[1] + ans[2] + l + l ) ;
}
return jean ;
}
