//#include "grader.cpp"
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fr first
#define sc second
#define all(s) s.begin(), s.end()
#define pi pair < int, int >
const int MN = 5e5 + 7;
const ll INF = 1e18 + 7;
ll d[MN];
int sb[MN], mx[MN], del[MN];
int n;
vector < pi > g[MN];
vector < pair < int, ll > > q[MN];
void dfs (int v, int sz, int p = 0){
sb[v] = 1;
mx[v] = 0;
for (pi to : g[v]){
if (!del[to.fr] && to.fr != p){
dfs(to.fr, sz, v);
sb[v] += sb[to.fr];
mx[v] = max(mx[v], sb[to.fr]);
}
}
mx[v] = max(mx[v], sz - sb[v]);
// cout << v << ' ' << sb[v] << ' ' << mx[v] << endl;
}
int fc (int v, int sz){
while (true){
int nv = v;
if (mx[v] <= sz / 2)
break;
for (pi to : g[v]){
if (!del[to.fr] && mx[to.fr] < mx[v]){
v = to.fr;
break;
}
}
if (nv == v)
break;
}
return v;
}
void mark (int v, int st, ll dis = 0, int p = 0){
q[v].pb({st, dis});
for (pi to : g[v]){
if (to.fr != p && !del[to.fr]){
mark(to.fr, st, dis + to.sc, v);
}
}
}
void cent (int v, int sz){
dfs(v, sz);
v = fc(v, sz);
mark(v, v);
del[v] = 1;
for (pi to : g[v]){
if (!del[to.fr]){
if (sb[to.fr] < sb[v])
cent(to.fr, sb[to.fr]);
else
cent(to.fr, sz - sb[v]);
}
}
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for (int i = 0; i < n - 1; i++){
g[A[i] + 1].pb({B[i] + 1, D[i]});
g[B[i] + 1].pb({A[i] + 1, D[i]});
}
cent(1, n);
memset(d, 0x3f3f3f3f, sizeof(d));
}
long long Query(int S, int X[], int T, int Y[]){
ll ans = INF;
for (int i = 0; i < S; i++){
int v = X[i] + 1;
for (auto it : q[v]){
d[it.fr] = min(d[it.fr], it.sc);
}
}
for (int i = 0; i < T; i++){
int v = Y[i] + 1;
for (auto it : q[v]){
ans = min(ans, d[it.fr] + it.sc);
}
}
for (int i = 0; i < S; i++){
int v = X[i] + 1;
for (auto it : q[v]){
d[it.fr] = INF;
}
}
return ans;
}
