#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define X first
#define Y second
const int maxn = 5e3 + 5;
const int mlog = 19;
const int inf = 1e9;
int n;
vector<pii> way[maxn];
int h[maxn], par[maxn][21], dist[maxn][21];
int sz[maxn], used[maxn];
int cpar[maxn];
int far[maxn];
void dfs(int u, int last, int lval) {
h[u] = h[last] + 1;
par[u][0] = last; dist[u][0] = lval;
for(int i=1;i<=mlog;i++) {
par[u][i] = par[par[u][i-1]][i-1];
dist[u][i] = dist[u][i-1] + dist[par[u][i-1]][i-1];
}
for(auto t : way[u]) {
int v = t.X, val = t.Y;
if(v==last) continue;
dfs(v, u, val);
}
}
int lca(int u, int v) {
int res = 0;
if(h[u]<h[v]) swap(u, v);
for(int i=mlog;i>=0;i--) {
if(h[par[u][i]]>=h[v]) {
res += dist[u][i];
u = par[u][i];
}
}
if(u==v) return res;
for(int i=mlog;i>=0;i--) {
if(par[u][i]!=par[v][i]) {
res += dist[u][i] + dist[v][i];
u = par[u][i]; v = par[v][i];
}
}
return res + dist[u][0] + dist[v][0];
}
void survey(int u, int last) {
sz[u] = 1;
for(auto t : way[u]) {
int v = t.X;
if(v==last || used[v]) continue;
survey(v, u);
sz[u] += sz[v];
}
}
int decom(int u) {
survey(u,0);
int x = u, last = 0;
redo:
for(auto t : way[x]) {
int y = t.X;
if(y==last || used[y]) continue;
if(sz[y]>=sz[u]/2) {
last = x; x = y;
goto redo;
}
}
used[x] = 1;
for(auto t : way[x]) {
int y = t.X;
if(used[y]) continue;
int temp = decom(y);
cpar[temp] = x;
}
return x;
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for(int i=0;i<n-1;i++) {
int x = A[i]+1, y = B[i]+1, val = D[i];
way[x].push_back({y,val});
way[y].push_back({x,val});
}
dfs(1,0,0);
decom(1);
for(int i=1;i<=n;i++) far[i] = inf;
}
long long Query(int S, int X[], int T, int Y[]) {
for(int i=0;i<T;i++) {
int u = Y[i]+1, x = u;
while(x) {
far[x] = min(far[x], lca(x, u));
x = cpar[x];
}
}
int res = inf;
for(int i=0;i<S;i++) {
int u = X[i]+1, x = u;
while(x) {
res = min(res, far[x] + lca(x,u));
x = cpar[x];
}
}
for(int i=0;i<T;i++) {
int u = Y[i]+1, x = u;
while(x) {
far[x] = inf;
x = cpar[x];
}
}
return res;
}
