#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
typedef long long ll;
const int maxn = 5e5+5;
const ll inf = 1e18;
vector<pair<int, int>> tree[maxn];
vector<int> graph[maxn];
int crr;
int st[20][2*maxn];
int lg[2*maxn], L[maxn], R[maxn];
int mm[2][maxn];
ll dp[2][maxn];
ll d1[maxn], d2[maxn];
ll ans;
int mn(int a, int b){
return d1[a] < d1[b] ? a : b;
}
bool cmp(int a, int b){return L[a] < L[b];}
bool insub(int a, int b){
return L[b] <= L[a] && R[b] >= L[a];
}
void pre_dfs(int x, int p = -1){
st[0][++crr]=x;
L[x]=crr;
d1[x]=d1[p]+1;
for(auto v: tree[x]){
if(v.f == p)continue;
d2[v.f]=d2[x]+v.s;
pre_dfs(v.f, x);
st[0][++crr]=x;
}
R[x] = crr;
}
void build(){
for(int i = 2; i <= crr; i++)lg[i] = lg[i>>1]+1;
for(int i = 1; i < 20; i++){
for(int j = 1; j <= crr; j++){
if(j+(1<<i)-1 > crr)break;
st[i][j] = mn(st[i-1][j], st[i-1][j+(1<<(i-1))]);
}
}
}
int LCA(int a, int b){
//cout << a << " " << b << endl;
int l = min(L[a], L[b]), r = max(R[a], R[b]), d = lg[r-l+1];
return mn(st[d][l], st[d][r-(1<<d)+1]);
}
void dfs(int x){
if(mm[0][x])dp[0][x]=0;
if(mm[1][x])dp[1][x]=0;
//cout << x << " " << dp[0][x] << " " << dp[1][x] << endl;
for(auto v: graph[x]){
dfs(v);
dp[0][x] = min(dp[0][v]+d2[v]-d2[x], dp[0][x]);
dp[1][x] = min(dp[1][v]+d2[v]-d2[x], dp[1][x]);
}
ans = min(ans, dp[0][x] + dp[1][x]);
}
void Init(int N, int A[], int B[], int D[]) {
crr = 0;
for(int i = 0; i < N-1; i++){
tree[A[i]].push_back({B[i], D[i]});
tree[B[i]].push_back({A[i], D[i]});
}
pre_dfs(1);
build();
}
long long Query(int S, int X[], int T, int Y[]) {
vector<int> nd;
ans = inf;
for(int i = 0; i < S; i++){
nd.push_back(X[i]);
mm[0][X[i]]=1;
}
for(int i = 0; i < T; i++){
nd.push_back(Y[i]);
mm[1][Y[i]]=1;
}
sort(nd.begin(), nd.end(), cmp);
for(int i = 0; i < S+T-1; i++){
nd.push_back(LCA(nd[i], nd[i+1]));
}
sort(nd.begin(), nd.end(), cmp);
nd.erase(unique(nd.begin(), nd.end()), nd.end());
stack<int> stk;
for(auto v: nd){
dp[0][v]=dp[1][v]=inf;
}
stk.push(nd[0]);
for(int i = 1; i < nd.size(); i++){
while(!insub(nd[i], stk.top()))stk.pop();
graph[stk.top()].push_back(nd[i]);
stk.push(nd[i]);
}
dfs(nd[0]);
for(auto v: nd){
mm[0][v]=mm[1][v]=0;
graph[v].clear();
}
return ans;
}
