#include <bits/stdc++.h>
using namespace std;
#define int long long
#define re real()
#define im imag()
#define pb push_back
#define stMn(a,b) a = min(a,b)
typedef complex<int> ii;
#define rep(i, a, b) for(int i = a; i < b; i++)
#define MAXN 501210
#define MAXH 20
#define INF 121020103141542069
vector<ii> adj[MAXN];
int ctrP[MAXN], sbtree[MAXN], ctrH[MAXN], fEuler[MAXN], sparsetable[2*MAXN][MAXH], cnt;
int logn[2 * MAXN];
int dst[MAXN], mnDst[MAXN];
void dfs_reg(int x, int par) {
sparsetable[cnt][0] = dst[x];
fEuler[x] = cnt++;
for(auto i: adj[x]) if(i.re != par) {
dst[i.re] = dst[x] + i.im;
dfs_reg(i.re, x);
sparsetable[cnt++][0] = dst[x];
}
}
void fnd() {
logn[1] = 0;
rep(i, 2, 2 * MAXN) logn[i] = logn[i/2] + 1;
}
void constructST() {
rep(i, 1, MAXH) rep(j, 0, 2 * MAXN) {
if(j <= 2 * MAXN - (1<<i)) {
sparsetable[j][i] = min(sparsetable[j][i-1], sparsetable[j+(1<<(i-1))][i-1]);
}
}
}
int lca(int a, int b) {
if(fEuler[a] > fEuler[b]) swap(a, b);
if(a == b) sparsetable[fEuler[a]][0];
int df = fEuler[b] - fEuler[a] + 1;
int h = logn[df];
return min(sparsetable[fEuler[a]][h],sparsetable[fEuler[b]+1-(1<<h)][h]);
}
int dfs_sb3(int x, int par) {
sbtree[x] = 1;
for(auto i: adj[x]) if(i.re != par && ctrH[i.re] == -1) {
sbtree[x] += dfs_sb3(i.re, x);
}
return sbtree[x];
}
int dfs_ctr(int u, int p, int n) {
for (auto v : adj[u]) if(ctrH[v.re] == -1) {
if (v.re != p && sbtree[v.re] > n / 2) {
return dfs_ctr(v.re, u, n);
}
}
return u;
}
void ctr3(int u, int p, int l) {
int n = dfs_sb3(u, p);
int cent = dfs_ctr(u, p, n);
ctrP[cent] = p;
ctrH[cent] = l;
for (auto v : adj[cent]) {
if (ctrH[v.re] != -1) continue;
ctr3(v.re, cent, l + 1);
}
}
void Init(int32_t N, int32_t A[], int32_t B[], int32_t D[]) {
fnd();
rep(i, 0, N - 1) {
adj[A[i]].pb(ii(B[i], D[i]));
adj[B[i]].pb(ii(A[i], D[i]));
}
rep(i, 0, MAXN) {
ctrH[i] = -1;
mnDst[i] = INF;
}
dfs_reg(0, -1); constructST();
ctr3(0, -1, 0);
}
int Query(int32_t S, int32_t X[], int32_t T, int32_t Y[]) {
vector<int> v;
rep(i, 0, S) {
int cur = X[i];
while(cur != -1) {
v.pb(cur);
stMn(mnDst[cur], dst[cur] + dst[X[i]] - 2 * lca(cur, X[i]));
cur = ctrP[cur];
}
}
int ans = INF;
rep(i, 0, T) {
int cur = Y[i];
while(cur != -1) {
stMn(ans,mnDst[cur] + dst[cur] + dst[Y[i]] - 2 * lca(cur, Y[i]));
cur = ctrP[cur];
}
}
for(auto i: v) mnDst[i] = INF;
return ans;
}
