#include "factories.h"
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
#define ld long double
#define pii pair<int,int>
#define sz(x) (int)x.size()
#define piii pair<pii,pii>
#define precise cout<<fixed<<setprecision(10)
#define st first
#define nd second
#define ins insert
#define vi vector<int>
#define BOOST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int MAX=5e5+5;
const ll inf=(ll)1e18+9;
const int STALA=19;
int A[MAX][STALA];
bool blocked[MAX];
int rwdc[MAX];
int sub[MAX];
vi PC[MAX];
vector<pii> P[MAX];
ll dist[MAX];
int ojciec[MAX];
int gle[MAX];
int n;
int dfs(int u,int fa){
sub[u]=1;
for (auto it:P[u]) if (it.st!=fa && !blocked[it.st]) sub[u]+=dfs(it.st,u);
return sub[u];
}
int find_centroid(int u,int fa,int ile){
for (auto it:P[u]) if (it.st!=fa && !blocked[it.st] && sub[it.st]>ile/2)return find_centroid(it.st,u,ile);
return u;
}
void centroid(int u,int fa){
int roz=dfs(u,fa);
int next_centroid=find_centroid(u,fa,roz);
rwdc[next_centroid]=fa;
blocked[next_centroid]=true;
for (auto it:P[next_centroid]){
if (blocked[it.st])continue;
centroid(it.st,next_centroid);
}
}
void dfs1(int u,int fa){
ojciec[u]=fa;
for (auto it:P[u]) if (it.st!=fa)gle[it.st]=gle[u]+1,dist[it.st]=dist[u]+it.nd,dfs1(it.st,u);
}
void make(int n){
for (int i=1;i<=n;i++)A[i][0]=ojciec[i];
for (int i=1;i<STALA;i++) for (int j=1;j<=n;j++) A[j][i]=A[A[j][i-1]][i-1];
}
int lca(int a,int b){
if (gle[a]>gle[b])swap(a,b);
for (int i=STALA-1;i>=0;i--)if (gle[A[b][i]]>=gle[a])b=A[b][i];
if (a==b)return a;
for (int i=STALA-1;i>=0;i--)if (A[a][i]!=A[b][i])a=A[a][i],b=A[b][i];
return ojciec[a];
}
ll distance(int a,int b){
return dist[b]+dist[a]-dist[lca(a,b)]*2;
}
ll d1[MAX];
ll d2[MAX];
void Init(int N,int A[],int B[],int D[]){
n=N;
for (int i=1;i<=n;i++){
d1[i]=d2[i]=inf;
}
for (int i=0;i<n-1;i++){
A[i]++;
B[i]++;
P[A[i]].pb(mp(B[i],D[i]));
P[B[i]].pb(mp(A[i],D[i]));
}
centroid(1,-1);
dfs1(1,1);
make(n);
}
ll Query(int S,int X[],int T,int Y[]){
ll ans=inf;
for (int i=0;i<S;i++)X[i]++;
for (int i=0;i<T;i++)Y[i]++;
for (int i=0;i<S;i++){
int u=X[i];
while (u!=-1){
// cout<<"TERAZ "<<u<<" "<<X[i]<<" "<<distance(u,X[i])<<" "<<lca(u,X[i])<<"\n";
d1[u]=min(d1[u],distance(u,X[i]));
u=rwdc[u];
}
}
int ile=0;
for (int i=0;i<T;i++){
int u=Y[i];
ile++;
while (u!=-1){
d2[u]=min(d2[u],distance(u,Y[i]));
ans=min(ans,d1[u]+d2[u]);
u=rwdc[u];
}
assert(ile<=n);
}
for (int i=0;i<S;i++){
int u=X[i];
while (u!=-1){
d1[u]=inf;
//d2[u]=inf;
u=rwdc[u];
}
}
for (int i=0;i<T;i++){
int u=Y[i];
while (u!=-1){
// d1[u]=inf;
d2[u]=inf;
u=rwdc[u];
}
}
return ans;
}
