#include <iostream>
#include <vector>
#include "factories.h"
#include <algorithm>
using namespace std;
const int M = 500005;
vector<pair<int,int>> nei[M];
int hei[M], par[M][20], st[M], en[M], ind, cur = 1;
long long Min[M][2], dist[M], inf = 1e17, Ans;
void dfs0(int u, int p){
hei[u] = (p == -1 ? 0 : hei[p]) + 1;
par[u][0] = p;
for (int i=1;i<20;i++)
par[u][i] = (par[u][i-1] == -1 ? -1 : par[par[u][i-1]][i-1]);
st[u] = cur++;
for (auto [i, w] : nei[u]){
if (i == p)
continue;
dist[i] = dist[u] + w;
dfs0(i, u);
}
Min[u][0] = Min[u][1] = inf;
en[u] = cur;
}
void Init(int n, int a[], int b[], int c[]){
for (int i=0;i<n-1;i++){
nei[a[i]].push_back({b[i], c[i]});
nei[b[i]].push_back({a[i], c[i]});
}
dfs0(0, -1);
}
int moveUp(int v, int d){
for (int i=0;i<20;i++)
if ((1<<i) & d)
v = par[v][i];
return v;
}
int LCA(int u, int v){
if (hei[u] > hei[v])
swap(u, v);
v = moveUp(v, hei[v] - hei[u]);
if (v == u)
return v;
for (int i=19;i>=0;i--)
if (par[v][i] != par[u][i])
u = par[u][i], v = par[v][i];
return par[u][0];
}
void merge(int a, int b, long long c){
Ans = min(Ans, min(Min[a][1] + Min[b][0], Min[b][1] + Min[a][0]) + c);
Min[a][1] = min(Min[a][1], Min[b][1] + c);
Min[a][0] = min(Min[a][0], Min[b][0] + c);
}
void dfs(vector<pair<int,int>> &t2, int u){
while (ind < t2.size() and t2[ind].first < en[u]){
int v = t2[ind++].second;
dfs(t2, v);
merge(u, v, dist[v] - dist[u]);
}
}
long long Query(int s, int x[], int t, int y[]){
Ans = inf;
vector<pair<int,int>> t2;
for (int i=0;i<s;i++)
t2.push_back({st[x[i]], x[i]}), Min[x[i]][0] = 0, Min[x[i]][1] = inf;
for (int i=0;i<t;i++)
t2.push_back({st[y[i]], y[i]}), Min[y[i]][1] = 0, Min[y[i]][0] = inf;
sort(begin(t2), end(t2));
for (int i=1;i<s+t;i++){
if (t2[i-1] == t2[i])
Ans = 0;
int lca = LCA(t2[i-1].second, t2[i].second);
t2.push_back({st[lca], lca});
}
sort(begin(t2), end(t2));
t2.resize(unique(begin(t2), end(t2)) - begin(t2));
ind = 1;
dfs(t2, t2[0].second);
for (auto [vl, i] : t2)
Min[i][0] = Min[i][1] = inf;
return Ans;
}
