#include "bits/stdc++.h"
#include "factories.h"
using namespace std;
#define MAXN 500005
#define ll long long
#define f first
#define s second
#define SZ(v) (int)v.size()
const ll inf = 1e16;
ll n, tim = 1, tin[MAXN], sp[MAXN][25], ans, sd[MAXN][25], lvl[MAXN], red[MAXN], blue[MAXN], d1[MAXN], d2[MAXN];
vector <pair <ll,ll>> E[MAXN], G[MAXN];
vector <ll> nd, h;
bool cmp(int x,int y) {
return (tin[x] < tin[y]);
}
void dfs(int x,int pr) {
tin[x] = tim++;
for(auto k : E[x]) {
ll i = k.f, j = k.s;
if(i == pr) continue;
sp[i][0] = x;
sd[i][0] = j;
lvl[i] = lvl[x] + 1;
dfs(i, x);
}
}
pair <ll,ll> kth_anc(int x,int y) {
ll s = 0;
for(int i = 20; i >= 0; i--) {
if((y >> i) & 1) {
s += sd[x][i];
x = sp[x][i];
}
}
return {x, s};
}
pair <ll,ll> find_anc(int x,int y) {
pair <ll,ll> a1 = {x,0}, a2 = {y,0};
if(lvl[x] < lvl[y]) {
a2 = kth_anc(y, lvl[y] - lvl[x]);
y = a2.f;
}
if(lvl[y] < lvl[x]){
a1 = kth_anc(x, lvl[x] - lvl[y]);
x = a1.f;
}
if(x == y) return {x, a1.s + a2.s};
ll S = 0;
for(int i = 20; i >= 0; i--) {
if(sp[x][i] != sp[y][i]) {
S += sd[x][i];
S += sd[y][i];
x = sp[x][i];
y = sp[y][i];
}
}
return {sp[x][0], S + sd[x][0] + sd[y][0]};
}
void solve(int nod,int pr) {
if(blue[nod]) d1[nod] = 0;
if(red[nod]) d2[nod] = 0;
for(auto k : G[nod]) {
ll i = k.f, j = k.s;
if(i == pr) continue;
solve(i, nod);
d1[nod] = min(d1[nod], d1[i] + j);
d2[nod] = min(d2[nod], d2[i] + j);
}
if(d1[nod] != inf && d2[nod] != inf)ans = min(ans, d1[nod] + d2[nod]);
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for(int i = 0; i < n - 1; i++) {
E[A[i]].push_back({B[i], D[i]});
E[B[i]].push_back({A[i], D[i]});
}
dfs(0, -1);
for(int j = 1; j <= 20; j++) {
for(int i = 0; i < n; i++) {
sp[i][j] = sp[sp[i][j - 1]][j - 1];
sd[i][j] = sd[i][j - 1] + sd[sp[i][j - 1]][j - 1];
}
}
}
long long Query(int S, int X[], int T, int Y[]) {
h.clear();
nd.clear();
ans = inf;
for(int i = 0; i < S; i++) {
nd.push_back(X[i]);
red[X[i]] = 1;
}
for(int i = 0; i < T; i++){
nd.push_back(Y[i]);
blue[Y[i]] = 1;
}
sort(nd.begin(),nd.end(), cmp);
h = nd;
for(int i = 0; i < SZ(nd) - 1; i++) {
auto F = find_anc(nd[i], nd[i + 1]);
h.push_back(F.f);
}
sort(h.begin(), h.end());
h.erase(unique(h.begin(), h.end()), h.end());
sort(h.begin(),h.end(), cmp);
stack <ll> st;
ll root = 0;
for(auto i : h) {
d1[i] = d2[i] = inf;
while(!st.empty() && find_anc(st.top(), i).f != st.top()) {
st.pop();
}
if(!st.empty()) {
auto val = find_anc(st.top(), i);
G[val.f].push_back({i, val.s});
G[i].push_back({val.f, val.s});
}
else root = i;
st.push(i);
}
solve(root, -1);
for(auto i : h) {
G[i].clear();
red[i] = blue[i] = d1[i] = d2[i] = 0;
}
return ans;
}
