#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#include "factories.h"
set<pair<llo,llo>> adj[500001];
llo ss[22][500001];
llo par[500001];
llo rr=0;
llo mi[500001];
llo ma[500001];
llo dist[500001][25];
llo cur;
llo dfs(llo no,llo parr=-1){
ss[cur][no]=1;
for(auto j:adj[no]){
if(j.a==parr){
continue;
}
dfs(j.a,no);
ss[cur][no]+=ss[cur][j.a];
}
}
llo dfs2(llo no,llo parr=-1,llo lev=0){
dist[cur][no]=lev;
//cout<<cur<<".."<<no<<".."<<lev<<endl;
for(auto j:adj[no]){
if(j.a==parr){
continue;
}
dfs2(j.a,no,lev+j.b);
}
}
llo find(llo no,llo par4=-1,llo wow=0){
llo st=0;
// cout<<no<<":";
for(auto j:adj[no]){
if(j.a==par4){
continue;
}
if(ss[cur][j.a]>ss[cur][rr]/2){
st=1;
return find(j.a,no,wow+j.b);
}
}
if(st==0){
return no;
}
}
llo dec(llo no,llo parc=-1,llo pop=0){
rr=no;
cur=pop;
dfs(no);
llo cen=find(no);
//llo cen=no;
dfs2(cen);
for(auto j:adj[cen]){
adj[j.a].erase({cen,j.b});
}
par[cen]=parc;
for(auto j:adj[cen]){
dec(j.a,cen,pop+1);
}
}
void Init(int nn,int aa[],int bb[],int dd[]){
llo n=(llo)nn;
memset(dist,-1,sizeof(dist));
for(llo i=0;i<n;i++){
ma[i]=-1;
mi[i]=-1;
}
for(llo i=0;i<n-1;i++){
adj[(llo)aa[i]].insert({(llo)bb[i],(llo)dd[i]});
adj[(llo)bb[i]].insert({(llo)aa[i],(llo)dd[i]});
}
dec(0);
/*for(llo i=0;i<n;i++){
cout<<par[i]<<","<<ww[i]<<endl;
}*/
}
llo Query(int s,int x[],int t,int y[]){
llo ans=-1;
for(llo i=0;i<(llo)s;i++){
llo no=(llo)x[i];
llo count=0;
while(no!=-1){
no=par[no];
count+=1;
}
no=(llo)x[i];
llo pc=0;
while(no!=-1){
if(mi[no]==-1){
mi[no]=dist[count-pc-1][(llo)x[i]];
}
else{
mi[no]=min(mi[no],dist[count-pc-1][(llo)x[i]]);
}
no=par[no];
pc+=1;
}
}
for(llo i=0;i<(llo)t;i++){
llo no=(llo)y[i];
llo count=0;
while(no!=-1){
no=par[no];
count+=1;
}
no=(llo)y[i];
llo pc=0;
while(no!=-1){
if(ma[no]==-1){
ma[no]=dist[count-pc-1][(llo)y[i]];
}
else{
ma[no]=min(ma[no],dist[count-pc-1][(llo)y[i]]);
}
if(mi[no]!=-1){
if(ans==-1){
ans=mi[no]+ma[no];
}
else{
ans=min(ans,mi[no]+ma[no]);
}
}
no=par[no];
pc+=1;
}
}
for(llo i=0;i<(llo)s;i++){
llo no=(llo)x[i];
llo tot=0;
while(no!=-1){
mi[no]=-1;
no=par[no];
}
}
for(llo i=0;i<(llo)t;i++){
llo no=(llo)y[i];
llo tot=0;
while(no!=-1){
ma[no]=-1;
no=par[no];
}
}
if(ans==0){
while(true){
continue;
}
}
return ans;
}
/*int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,q;
cin>>n>>q;
int aa[n];
int bb[n];
int dd[n];
for(llo i=0;i<n-1;i++){
cin>>aa[i]>>bb[i]>>dd[i];
}
Init(n,aa,bb,dd);
for(int i=0;i<q;i++){
int s,t;
cin>>s>>t;
int ac[s];
int bc[t];
for(int j=0;j<s;j++){
cin>>ac[j];
}
for(int j=0;j<t;j++){
cin>>bc[j];
}
cout<<Query(s,ac,t,bc)<<endl;
}
return 0;
}*/
