#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pi pair<int,int>
#define pb push_back
#define all(a) begin(a), end(a)
const ll inf = 1e18;
const int mxn = 5e5+10, lg2 = 19;
vector<pi> g[mxn];
int suc[mxn][lg2];
int tin[mxn], tout[mxn], tim = 0;
ll dep[mxn], dp[mxn][2];
void dfs(int u, int p, ll dis){
suc[u][0] = p, dep[u] = dis;
for(int i = 1; i < lg2; i++)
suc[u][i] = suc[suc[u][i-1]][i-1];
tin[u] = tim++;
for(auto [v,c] : g[u]) if(v!=p)
dfs(v,u,dis+c);
tout[u] = tim++; g[u].clear();
}
bool is_anc(int u, int v){
return tin[u]<=tin[v] && tout[v]<=tout[u];
}
int get_lca(int u, int v){
if(is_anc(u,v)) return u;
if(is_anc(v,u)) return v;
for(int i = lg2-1; i>=0; i--)
if(!is_anc(suc[u][i],v))
u = suc[u][i];
return suc[u][0];
}
bool cmp(int u, int v){
return tin[u] < tin[v];
}
void Init(int N, int A[], int B[], int D[]) {
for(int i = 0; i < N-1; i++){
g[A[i]].pb({B[i],D[i]});
g[B[i]].pb({A[i],D[i]});
dp[i][0] = dp[i][1] = inf;
}
dp[N-1][0] = dp[N-1][1] = inf;
dfs(0,0,0);
}
long long Query(int S, int X[], int T, int Y[]) {
vector<int> vec;
for(int i = 0; i < S; i++){
dp[X[i]][0] = dep[X[i]]; vec.pb(X[i]);
}
for(int i = 0; i < T; i++){
dp[Y[i]][1] = dep[Y[i]]; vec.pb(Y[i]);
}
sort(all(vec),cmp);
for(int i = 0; i < S+T-1; i++)
vec.pb(get_lca(vec[i],vec[i+1]));
sort(all(vec),cmp); vec.erase(unique(all(vec)),vec.end());
stack<int> st;
for(auto u : vec){
while(!st.empty() && !is_anc(st.top(),u)) st.pop();
if(!st.empty()) g[st.top()].pb({u,0});
st.push(u);
}
reverse(all(vec));
ll ans = inf;
for(auto u : vec){
for(auto [v,c] : g[u]){
dp[u][0] = min(dp[u][0],dp[v][0]);
dp[u][1] = min(dp[u][1],dp[v][1]);
}
ans = min(ans,dp[u][0] + dp[u][1] - 2*dep[u]);
}
for(auto u : vec){
g[u].clear(); dp[u][0] = dp[u][1] = inf;
}
return ans;
}
