#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[500001];
llo par[500001];
llo rr=0;
llo mi[500001];
//llo ma[500001];
llo dist[22][500001];
//llo vis[500001];
llo lol[500001];
llo cur;
void dfs(llo no,llo parr=-1){
ss[no]=1;
for(auto j:adj[no]){
if(j.a==parr){
continue;
}
dfs(j.a,no);
ss[no]+=ss[j.a];
}
}
void dfs2(llo no,llo parr=-1,llo lev=0,llo cur2=0){
dist[cur2][no]=lev;
// cout<<cur2<<".."<<no<<".."<<lev<<endl;
for(auto j:adj[no]){
if(j.a==parr){
continue;
}
dfs2(j.a,no,lev+j.b,cur2);
}
}
llo find(llo no,llo par4=-1){
llo st=0;
// cout<<no<<":";
for(auto j:adj[no]){
if(j.a==par4){
continue;
}
if(ss[j.a]>ss[rr]/2){
st=1;
return find(j.a,no);
}
}
if(st==0){
return no;
}
}
void dec(llo no,llo parc=-1,llo pop=0){
rr=no;
cur=pop;
dfs(no);
llo cen=find(no);
lol[cen]=pop;
//llo cen=no;
dfs2(cen,-1,0,pop);
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;
// for(llo i=0;i<n;i++){
// vis[i]=0;
/* for(llo j=0;j<21;j++){
dist[j][i]=-1;
}*/
// }
for(llo i=0;i<n;i++){
// ma[i]=-1;
mi[i]=-1;
}
for(llo i=0;i<n-1;i++){
adj[aa[i]].insert({(llo)bb[i],(llo)dd[i]});
adj[bb[i]].insert({(llo)aa[i],(llo)dd[i]});
}
dec(0);
/*for(llo i=0;i<n;i++){
cout<<par[i]<<":"<<endl;
}*/
}
llo Query(int s,int x[],int t,int y[]){
llo ans=-1;
vector<llo> rem;
for(llo i=0;i<(llo)s;i++){
llo no;
no=(llo)x[i];
llo pc=0;
while(no!=-1){
if(mi[no]==-1){
mi[no]=dist[lol[x[i]]-pc][(llo)x[i]];
}
else{
mi[no]=min(mi[no],dist[lol[x[i]]-pc][(llo)x[i]]);
}
rem.pb(no);
no=par[no];
pc+=1;
}
}
for(llo i=0;i<(llo)t;i++){
llo no;
no=(llo)y[i];
llo pc=0;
while(no!=-1){
if(mi[no]!=-1 ){
if(ans==-1){
ans=mi[no]+dist[lol[y[i]]-pc][(llo)y[i]];
}
else{
ans=min(ans,mi[no]+dist[lol[y[i]]-pc][(llo)y[i]]);
}
}
no=par[no];
pc+=1;
}
}
for(auto j:rem){
// ma[j]=-1;
mi[j]=-1;
}
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)<<'\n';
}
return 0;
}*/
