#include "factories.h"
#define fi first
#define se second
#define ll long long
#define pii pair<ll, ll>
#include <bits/stdc++.h>
using namespace std;
const ll M = 5e3+3, R=1e14;
int n;
vector<pii> graf[M];
bool ix[M], iy[M];
ll dx[M], dy[M];
ll dfs(int v, int p)
{
if(!ix[v]) dx[v] = R;
if(!iy[v]) dy[v] = R;
ll ret = R;
for(auto [x,d]: graf[v])
if(x != p)
{
ret = min(ret, dfs(x, v));
dx[v] = min(dx[v], dx[x]+d);
dy[v] = min(dy[v], dy[x]+d);
}
ret = min(ret, dx[v]+dy[v]);
return ret;
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for(int i=0; i<N; i++)
graf[A[i]].push_back({B[i], D[i]}),
graf[B[i]].push_back({A[i], D[i]});
}
long long Query(int S, int X[], int T, int Y[]) {
memset(ix,0,sizeof ix);
memset(iy,0,sizeof iy);
memset(dx,0,sizeof dx);
memset(dy,0,sizeof dy);
for(int i=0; i<S; i++)
ix[X[i]] = 1;
for(int j=0; j<T; j++)
iy[Y[j]] = 1;
return dfs(0, 0);
}
