#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
typedef long long ll;
/*
void openFiles() {
#ifdef KEK
assert(freopen("input.txt", "r", stdin));
assert(freopen("output.txt", "w", stdout));
#endif
}
*/
void IOoptimize() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
const int MAXN = 5e5 + 10;
const int MAXLOG = 20;
const ll INF = 1e17;
vector<pair<int, ll>> g[MAXN];
int n;
int type[MAXN];
ll dist[MAXN];
int jump[MAXLOG][MAXN];
ll sum[MAXLOG][MAXN];
bool second_group;
bool used[MAXN];
int h[MAXN];
void dfs(int u, int height) {
used[u] = true;
h[u] = height;
for (auto v : g[u]) {
if (!used[v.first]) {
jump[0][v.first] = u;
sum[0][v.first] = v.second;
dfs(v.first, height + 1);
}
}
}
bool get_bit(int mask, int i) {
return (mask & (1 << i));
}
ll get_dist(int x, int y) {
ll res = 0;
if (h[x] < h[y])
swap(x, y);
int diff = h[x] - h[y];
for (int i = 0; i < MAXLOG; i++) {
if (get_bit(diff, i)) {
res += sum[i][x];
x = jump[i][x];
}
}
if (x != y) {
for (int i = MAXLOG - 1; i >= 0; i--) {
if (jump[i][x] != jump[i][y]) {
res += sum[i][x];
res += sum[i][y];
x = jump[i][x];
y = jump[i][y];
}
}
res += sum[0][x];
res += sum[0][y];
}
return res;
}
void Init(int N, int A[], int B[], int D[]) {
IOoptimize();
n = N;
for (int i = 0; i < n - 1; i++) {
g[A[i]].push_back({B[i], D[i]});
g[B[i]].push_back({A[i], D[i]});
}
second_group = (n > 5000);
if (second_group) {
dfs(0, 0);
for (int k = 1; k < MAXLOG; k++) {
for (int i = 0; i < n; i++) {
jump[k][i] = jump[k - 1][jump[k - 1][i]];
sum[k][i] = sum[k - 1][i] + sum[k - 1][jump[k - 1][i]];
}
}
}
}
long long Query(int S, int X[], int T, int Y[]) {
if (second_group) {
ll ans = INF;
for (int i = 0; i < S; i++) {
for (int j = 0; j < T; j++) {
ans = min(ans, get_dist(X[i], Y[j]));
}
}
return ans;
}
else {
memset(type, 0, sizeof(type));
for (int i = 0; i < T; i++) {
type[Y[i]] = 1;
}
for (int i = 0; i < n; i++) {
dist[i] = INF;
}
set<pair<ll, int>> q;
for (int i = 0; i < S; i++) {
dist[X[i]] = 0;
q.insert({dist[X[i]], X[i]});
}
while (!q.empty()) {
int cur = q.begin()->second;
q.erase(q.begin());
if (type[cur] == 1) {
return dist[cur];
}
for (auto v : g[cur]) {
if (dist[v.first] > dist[cur] + v.second) {
q.erase({dist[v.first], v.first});
dist[v.first] = dist[cur] + v.second;
q.insert({dist[v.first], v.first});
}
}
}
}
return INF;
}
