#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
typedef long long ll;
const int N = (int) 5e5 + 7;
const int K = 21;
int n;
int indexOfNode[N];
int currentIndex;
int secondCurrentIndex;
int dep[N];
int first[N];
int last[N];
int lg[2 * N];
vector<pair<int, int>> g[N];
pair<int, int> rmq[K][2 * N];
ll sum[N];
void addEdgeToGraph(int a, int b, int d) {
g[a].push_back({b, d});
g[b].push_back({a, d});
}
void build_stuff(int a, int p = 0) {
indexOfNode[a] = ++currentIndex;
rmq[0][++secondCurrentIndex] = {dep[a], a};
first[a] = secondCurrentIndex;
for (auto &it : g[a]) {
int b = it.first;
int cost = it.second;
if (b != p) {
dep[b] = 1 + dep[a];
sum[b] = cost + sum[a];
build_stuff(b, a);
rmq[0][++secondCurrentIndex] = {dep[a], a};
}
}
last[a] = secondCurrentIndex;
}
int getlca(int a, int b) {
if (first[a] > last[b]) {
swap(a, b);
}
a = first[a];
b = last[b];
assert(a <= b);
int k = lg[b - a + 1];
return min(rmq[k][a], rmq[k][b - (1 << k) + 1]).second;
}
void Init(int nn, int edges_a[], int edges_b[], int edges_d[]) {
n = nn;
for (int i = 1; i <= n; i++) {
g[i].clear();
}
for (int i = 0; i < n - 1; i++) {
addEdgeToGraph(edges_a[i] + 1, edges_b[i] + 1, edges_d[i]);
}
build_stuff(1);
for (int i = 2; i <= secondCurrentIndex; i++) {
lg[i] = 1 + lg[i / 2];
}
for (int k = 1; (1 << k) <= secondCurrentIndex; k++) {
for (int i = 1; i + (1 << k) - 1 <= secondCurrentIndex; i++) {
rmq[k][i] = min(rmq[k - 1][i], rmq[k - 1][i + (1 << (k - 1))]);
}
}
/*for (int i = 1; i <= n; i++) {
assert(getlca(i, i) == i);
for (int j = i + 1; j <= n; j++) {
cout << i << " " << j << " ---> " << getlca(i, j) << "\n";
assert(getlca(i, j) == getlca(j, i));
}
}*/
/*for (int i = 1; i <= n; i++) {
for (auto &it : g[i]) {
int j = it.first, c = it.second;
if (i < j) {
cout << i << " " << j << " " << c << "\n";
}
}
}*/
}
int valueOf[N], par[N], root;
vector<pair<int, ll>> secondg[N];
const ll INF = (ll) 1e18 + 7;
ll best;
ll mn1[N];
ll mn2[N];
void dfs(int a) {
mn1[a] = mn2[a] = INF;
if (valueOf[a] == 1) {
mn1[a] = 0;
}
if (valueOf[a] == 2) {
mn2[a] = 0;
}
for (auto &it : secondg[a]) {
int b = it.first;
ll c = it.second;
dfs(b);
mn1[a] = min(mn1[a], mn1[b] + c);
mn2[a] = min(mn2[a], mn2[b] + c);
}
best = min(best, mn1[a] + mn2[a]);
}
long long Query(int s, int x[], int t, int y[]) {
vector<pair<int, int>> guys;
for (int i = 0; i < s; i++) {
guys.push_back({indexOfNode[x[i] + 1], x[i] + 1});
valueOf[x[i] + 1] = 1;
}
for (int i = 0; i < t; i++) {
guys.push_back({indexOfNode[y[i] + 1], y[i] + 1});
valueOf[y[i] + 1] = 2;
}
sort(guys.begin(), guys.end());
vector<pair<int, int>> secondGuys = guys;
for (int i = 1; i < (int) guys.size(); i++) {
int node = getlca(guys[i - 1].second, guys[i].second);
secondGuys.push_back({indexOfNode[node], node});
}
sort(secondGuys.begin(), secondGuys.end());
assert(!secondGuys.empty());
vector<int> path;
root = secondGuys[0].second;
par[root] = 0;
path.push_back(root);
for (int it = 1; it < (int) secondGuys.size(); it++) {
if (secondGuys[it] == secondGuys[it - 1]) {
continue;
}
int node = secondGuys[it].second;
while (1) {
assert(!path.empty());
int lca = getlca(node, path.back());
if (lca != path.back()) {
path.pop_back();
} else {
break;
}
}
par[node] = path.back();
path.push_back(node);
}
for (auto &it : secondGuys) {
secondg[par[it.second]].push_back({it.second, sum[it.second] - sum[par[it.second]]});
}
best = INF;
dfs(root);
for (auto &it : secondGuys) {
valueOf[it.second] = 0;
par[it.second] = 0;
secondg[it.second].clear();
}
return best;
}
