#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
#define pb push_back
#define f first
#define s second
const int LOGN = 19;
const int MAXN = 5e5 + 100;
const ll INF = 1e15;
vector<pi> aL[MAXN];
int anc[MAXN][LOGN];
int depth[MAXN];
ll rDist[MAXN];
int N;
void dfs(int cV, int pV) {
for (pi aE : aL[cV]) {
int aV = aE.f;
ll eC = aE.s;
if (aV != pV) {
depth[aV] = depth[cV] + 1;
rDist[aV] = rDist[cV] + eC;
dfs(aV, cV);
anc[aV][0] = cV;
}
}
}
void prep() {
anc[0][0] = 0;
for (int k = 1; k < LOGN; k++) {
for (int i = 0; i < N; i++) {
anc[i][k] = anc[anc[i][k - 1]][k - 1];
}
}
}
int j(int a, int d) {
for (int i = 0; i < LOGN; i++) {
if (d & (1 << i)) {
a = anc[a][i];
}
}
return a;
}
int fLCA(int a, int b) {
if (depth[a] > depth[b]) swap(a, b);
b = j(b, depth[b] - depth[a]);
if (a == b) return a;
for (int i = LOGN - 1; i >= 0; i--) {
if (anc[a][i] != anc[b][i]) {
a = anc[a][i];
b = anc[b][i];
}
}
return anc[a][0];
}
void Init(int iN, int A[], int B[], int D[]) {
N = iN;
for (int i = 0; i < N; i++) {
aL[A[i]].pb({B[i], D[i]});
aL[B[i]].pb({A[i], D[i]});
}
depth[0] = rDist[0] = 0;
dfs(0, -1);
prep();
}
ll ans;
ll best[MAXN][2];
void dfsAll(int cV, int pV) {
for (pi aE : aL[cV]) {
int aV = aE.f;
ll eC = aE.s;
if (aV != pV) {
dfsAll(aV, cV);
best[cV][0] = min(best[cV][0], best[aV][0] + eC);
best[cV][1] = min(best[cV][1], best[aV][1] + eC);
}
ans = min(ans, best[cV][0] + best[cV][1]);
}
}
ll Query(int S, int X[], int T, int Y[]) {
ans = INF;
if (S * T >= N) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < 2; j++) {
best[i][j] = INF;
}
}
for (int i = 0; i < S; i++) {
best[X[i]][0] = 0;
}
for (int i = 0; i < T; i++) {
best[Y[i]][1] = 0;
}
dfsAll(0, -1);
} else {
for (int i = 0; i < S; i++) {
for (int j = 0; j < T; j++) {
int lca = fLCA(X[i], Y[j]);
ll cur = rDist[X[i]] + rDist[Y[j]] - 2 * rDist[lca];
ans = min(ans, cur);
}
}
}
assert(ans >= 0);
return ans;
}
