#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std ;
#define MAXN 500007
#define LOG 20
int n ;
vector < pair < int , int > > v[ MAXN ] ;
long long dist[ MAXN ][ LOG + 1 ] ;
int LCA[ MAXN ][ LOG + 1 ] ;
int lvl[ MAXN ] ;
int subtree[ MAXN ] ;
int lst[ MAXN ] ;
int used[ MAXN ] ;
int tot = 0 ;
long long ans[ MAXN ] ;
int w[ MAXN ] ;
void dfs ( int vertex , int prv , int ori ) {
if ( used[ vertex ] == 1 ) { return ; }
tot ++ ;
int i ;
int sz = v[ vertex ].size ( ) ;
subtree[ vertex ] = 1 ;
for ( i = 0 ; i < sz ; i ++ ) {
if ( v[ vertex ][ i ].first == prv ) { continue ; }
if ( used[ v[ vertex ][ i ].first ] != 0 ) { continue ; }
dist[ v[ vertex ][ i ].first ][ w[ ori ] ] = dist[ vertex ][ w[ ori ] ] + v[ vertex ][ i ].second ;
dfs ( v[ vertex ][ i ].first , vertex , ori ) ;
subtree[ vertex ] += subtree[ v[ vertex ][ i ].first ] ;
}
}
int find_centroid ( int vertex , int prv ) {
int i ;
int sz = v[ vertex ].size ( ) ;
for ( i = 0 ; i < sz ; i ++ ) {
if ( v[ vertex ][ i ].first == prv ) { continue ; }
if ( used[ v[ vertex ][ i ].first ] == 0 && subtree[ v[ vertex ][ i ].first ] > ( tot / 2 ) ) {
return find_centroid ( v[ vertex ][ i ].first , vertex ) ;
}
}
return vertex ;
}
void decompose ( int vertex , int prv ) {
tot = 0 ;
if ( prv == -1 ) {
dfs ( vertex , -1 , 0 ) ;
}
else {
dfs ( vertex , -1 , prv ) ;
}
int cen = find_centroid ( vertex , -1 ) ;
lst[ cen ] = prv ;
used[ cen ] = 1 ;
if ( prv != -1 ) {
w[ cen ] = w[ prv ] + 1 ;
}
else {
w[ cen ] = 1 ;
}
int i , sz ;
sz = v[ cen ].size ( ) ;
for ( i = 0 ; i < sz ; i ++ ) {
if ( used[ v[ cen ][ i ].first ] == 0 ) {
dist[ v[ cen ][ i ].first ][ w[ cen ] ] = v[ cen ][ i ].second ;
decompose ( v[ cen ][ i ].first , cen ) ;
}
}
}
void update ( int vertex , int x ) {
while ( vertex != -1 ) {
long long cur = dist[ x ][ w[ vertex ] ] ;
if ( ans[ vertex ] == -1 ) { ans[ vertex ] = cur ; }
if ( ans[ vertex ] > cur ) { ans[ vertex ] = cur ; }
vertex = lst[ vertex ] ;
}
}
void reset ( int vertex ) {
while ( vertex != -1 ) {
ans[ vertex ] = -1 ;
vertex = lst[ vertex ] ;
}
}
long long query ( int vertex , int x ) {
long long ret = -1 ;
while ( vertex != -1 ) {
if ( ans[ vertex ] > -1 ) {
long long cur = dist[ x ][ w[ vertex ] ] + ans[ vertex ] ;
if ( ret == -1 ) { ret = cur ; }
if ( ret > cur ) { ret = cur ; }
}
vertex = lst[ vertex ] ;
}
return ret ;
}
void Init(int N, int A[], int B[], int D[]) {
n = N ;
int i ;
for ( i = 0 ; i < N - 1 ; i ++ ) {
A[ i ] ++ ;
B[ i ] ++ ;
v[ A[ i ] ].push_back ( make_pair ( B[ i ] , D[ i ] ) ) ;
v[ B[ i ] ].push_back ( make_pair ( A[ i ] , D[ i ] ) ) ;
}
decompose ( 1 , -1 ) ;
for ( i = 1 ; i <= n ; i ++ ) {
ans[ i ] = -1 ;
}
}
long long Query(int S, int X[], int T, int Y[]) {
int i ;
for ( i = 0 ; i < S ; i ++ ) {
X[ i ] ++ ;
}
for ( i = 0 ; i < T ; i ++ ) {
Y[ i ] ++ ;
}
for ( i = 0 ; i < S ; i ++ ) {
update ( X[ i ] , X[ i ] ) ;
}
long long ret = -1 ;
for ( i = 0 ; i < T ; i ++ ) {
long long cur = query ( Y[ i ] , Y[ i ] ) ;
if ( cur > -1 ) {
if ( ret == -1 ) { ret = cur ; }
if ( ret > cur ) { ret = cur ; }
}
}
for ( i = 0 ; i < S ; i ++ ) {
reset ( X[ i ] ) ;
}
return ret ;
}
