#include "dreaming.h"
#include <bits/stdc++.h>
#define endl "\n"
#define F first
#define S second
#define pb push_back
#define all(x) x.begin() , x.end()
typedef long long ll;
using namespace std;
const int N = 1e5+5;
const long long oo = 1e18 ;
vector <pair <ll,ll>> v[N] ;
vector <ll> vec ;
ll n , m , best , mx , dis[N] , len , ans ;
bool vis[N] ;
pair <ll,ll> dfs (ll u , ll p)
{
vis[u] = true ;
pair <ll,ll> ret = {0 , u} ;
for (auto it : v[u])
{
if (it.F == p) continue ;
pair <ll,ll> p = dfs(it.F , u) ;
p.F += it.S ;
ret = max(ret , p) ;
}
best = min(best , max(len - ret.F , ret.F) ) ;
return ret ;
}
ll get (ll p)
{
ll p1 ;
p1 = dfs(p , p).S ;
len = dfs(p1 , p1).F ;
ans = max(ans , len);
best = oo ;
dfs(p1 , p1) ;
return best ;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
n = N ; m = M ;
for (int i = 0 ; i<m ; i++)
{
v[B[i]].pb({A[i] , T[i]});
v[A[i]].pb({B[i] , T[i]});
}
for (int i = 0 ; i<n ; i++)
{
if (!vis[i])
vec.pb(get(i)) ;
}
sort (all(vec)); reverse(all(vec));
ans = max(ans , vec[0] + vec[1] + L) ;
if (vec.size() > 2)
ans = max (ans , vec[1] + vec[2] + L + L) ;
return ans ;
}
