#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
#define maxn 200009
#define fi first
#define se second
#define pb push_back
#define left id<<1
#define right id<<1|1
#define re exit(0);
const int INF = 1e9 ;
const int mod = 1e9+7 ;
typedef vector<int> vi ;
typedef pair<int,int> pii ;
typedef vector<pii> vii ;
template < typename T > void chkmin ( T &a , T b ) { if ( a > b ) a = b ; }
template < typename T > void chkmax ( T &a , T b ) { if ( a < b ) a = b ; }
int n , m ;
vii adjList [maxn] ;
vi vertices ;
bool visited [maxn] ;
int pos , best ;
int d [maxn] ;
int d1 [maxn] , d2 [maxn] ;
void dfs ( int u )
{
for ( auto x : vertices ) d [x] = INF ;
queue <int> q ;
q . push (u) ; d [u] = 0 ;
while ( !q.empty() )
{
int u = q.front() ; q.pop() ;
for ( auto x : adjList [u] )
{
int v = x.fi , w = x.se ;
if ( d [v] > d [u] + w ) q . push (v) , d [v] = d [u] + w ;
}
}
best = - 1 ;
for ( auto x : vertices ) if ( d [x] > best ) best = d [x] , pos = x ;
}
void reset ()
{
for ( int i = 1 ; i <= n ; i ++ ) adjList [i] . clear () ;
for ( int i = 1 ; i <= n ; i ++ ) visited [i] = false ;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n = N , m = M ;
reset () ;
for ( int i = 0 ; i < m ; i ++ )
{
int u = A [i] + 1 , v = B [i] + 1 , w = T [i] ;
adjList [u] . push_back ({v,w}) ;
adjList [v] . push_back ({u,w}) ;
}
vi diameter ;
for ( int i = 1 ; i <= n ; i ++ )
{
if ( visited [i] ) continue ;
vertices.clear () ;
queue <int> q ;
q . push (i) ; visited [i] = true ;
while ( !q.empty() )
{
int u = q.front() ; q.pop() ;
vertices . push_back (u) ;
for ( auto x : adjList [u] )
{
int v = x.fi , w = x.se ;
if ( visited [v] == false )
{
visited [v] = true ;
q . push (v) ;
}
}
}
dfs (vertices[0]) ;
dfs (pos) ;
for ( auto x : vertices ) d1 [x] = d [x] ;
dfs (pos) ;
for ( auto x : vertices ) d2 [x] = d [x] ;
int Min = INF ;
for ( auto x : vertices ) chkmin (Min,max(d1[x],d2[x])) ;
diameter . pb (Min) ;
}
sort (diameter.rbegin(),diameter.rend()) ;
int res = diameter[0] ;
if ( diameter.size () >= 2 ) res = max (res,diameter[0]+diameter[1]+L) ;
if ( diameter.size () >= 3 ) res = max (res,diameter[1]+diameter[2]+2*L) ;
return res ;
}
