#include "factories.h"
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define fi first
#define se second
using namespace std;
const int N = 5e5 + 5;
const ll INF = 1e18 + 5;
vector<pair<int,int> > g[N];
ll col[N], best;
void Init(int N, int A[], int B[], int D[])
{
for(int i = 0;i < N;i++)
{
int u = A[i], v = B[i], d = D[i];
g[u].pb({v, d});
g[v].pb({u, d});
}
}
pair<ll,ll> dfs(int u, int p)
{
ll min1 = (col[u] == 1 ? 0ll : INF), min2 = (col[u] == 2 ? 0ll : INF);
for(auto [v, d] : g[u])
{
if(v == p)
continue;
auto t = dfs(v, u);
min1 = min(min1, t.fi + d);
min2 = min(min2, t.se + d);
}
best = min(best, min1 + min2);
return {min1, min2};
}
ll Query(int S, int X[], int T, int Y[])
{
for(int i = 0;i < S;i++)
col[X[i]] = 1;
for(int i = 0;i < T;i++)
col[Y[i]] = 2;
best = INF;
dfs(0, 0);
for(int i = 0;i < S;i++)
col[X[i]] = 0;
for(int i = 0;i < T;i++)
col[Y[i]] = 0;
return best;
}
