#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
const int MaxN = 5e5 + 7;
const int Log = 20;
int dfn[MaxN], dfst, efn[MaxN], prt[Log][MaxN], dep[MaxN], c[1000005], xyzzzz[500005], cnt, pv;
long long d[MaxN], res;
vector<pair<int, int>> adj[MaxN];
void dfssss(int x, int p) {
dfn[x] = ++dfst;
for (auto i : adj[x]) {
if (i.second == p) {
continue;
}
dep[dfst + 1] = dep[dfn[x]] + 1;
d[dfst + 1] = d[dfn[x]] + i.first;
prt[0][dfst + 1] = dfn[x];
dfssss(i.second, x);
}
efn[dfn[x]] = dfst;
}
pair<long long, long long> dfs(int x) {
long long s = 1e18, t = 1e18;
if (xyzzzz[x] == 1) {
s = 0;
}
if (xyzzzz[x] == 2) {
t = 0;
}
xyzzzz[x] = 0;
while (pv < cnt && c[pv] <= efn[x]) {
int i = c[pv++];
auto pr = dfs(i);
s = min(s, pr.first + d[i] - d[x]);
t = min(t, pr.second + d[i] - d[x]);
}
res = min(res, s + t);
return {s, t};
}
int lca(int s, int e) {
if (dep[s] < dep[e]) {
swap(s, e);
}
for (int i = 18; i >= 0; i--) {
if ((dep[s] - dep[e] >> i) & 1) {
s = prt[i][s];
}
}
if (s == e) {
return s;
}
for (int i = 18; i >= 0; i--) {
if (prt[i][s] != prt[i][e]) {
s = prt[i][s];
e = prt[i][e];
}
}
return prt[0][s];
}
void Init(int N, int A[], int B[], int D[]) {
for (int i = 0; i < N - 1; i++) {
adj[A[i]].push_back({D[i], B[i]});
adj[B[i]].push_back({D[i], A[i]});
}
dfssss(0, 0);
for (int i = 1; i < 19; i++) {
for (int j = 1; j <= N; j++) {
prt[i][j] = prt[i - 1][prt[i - 1][j]];
}
}
}
long long Query(int S, int X[], int T, int Y[]) {
cnt = 0;
for (int i = 0; i < S; i++) {
c[cnt] = dfn[X[i]];
xyzzzz[c[cnt++]] = 1;
}
for (int i = 0; i < T; i++) {
c[cnt] = dfn[Y[i]], xyzzzz[c[cnt++]] = 2;
}
sort(c, c + cnt);
for (int i = cnt - 1; i >= 1; i--) {
c[cnt++] = lca(c[i - 1], c[i]);
}
sort(c, c + cnt);
cnt = unique(c, c + cnt) - c;
res = 1e18;
pv = 0;
dfs(1);
return res;
}
