#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500005;
const int LOG = 20;
const long long INF = 1e18;
vector<pair<int, int>> adj[MAXN];
vector<pair<long long, long long>> vtree[MAXN];
int up[MAXN][LOG];
int depth[MAXN];
long long dist[MAXN];
long long tin[MAXN], tout[MAXN], timer;
long long dp[MAXN];
bool vis[MAXN];
void dfs(int u, int p) {
up[u][0] = p;
for (int i = 1; i < LOG; ++i)
up[u][i] = up[up[u][i - 1]][i - 1];
tin[u] = ++timer;
for (auto &e : adj[u]) {
int v = e.first, w = e.second;
if (v != p) {
depth[v] = depth[u] + 1;
dist[v] = dist[u] + w;
dfs(v, u);
}
}
tout[u] = timer;
}
int lca(int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
for (int i = LOG - 1; i >= 0; --i)
if (depth[up[u][i]] >= depth[v])
u = up[u][i];
if (u == v) return u;
for (int i = LOG - 1; i >= 0; --i)
if (up[u][i] != up[v][i]) {
u = up[u][i];
v = up[v][i];
}
return up[u][0];
}
long long get_dist(int u, int v) {
int anc = lca(u, v);
return dist[u] + dist[v] - 2 * dist[anc];
}
bool is_ancestor(int u, int v) {
return tin[u] <= tin[v] && tout[v] <= tout[u];
}
void Init(int n, int A[], int B[], int D[]) {
for (int i = 0; i < n - 1; ++i) {
adj[A[i]].emplace_back(B[i], D[i]);
adj[B[i]].emplace_back(A[i], D[i]);
}
depth[0] = dist[0] = 0;
timer = 0;
dfs(0, 0);
fill(dp, dp + n, -1);
}
long long Query(int s, int X[], int t, int Y[]) {
vector<int> nodes;
for (int i = 0; i < s; ++i) nodes.push_back(X[i]);
for (int i = 0; i < t; ++i) {
nodes.push_back(Y[i]);
dp[Y[i]] = 0;
}
sort(nodes.begin(), nodes.end(), [](int a, int b) { return tin[a] < tin[b]; });
vector<int> unique_nodes = nodes;
for (int i = 1; i < (int)nodes.size(); ++i)
unique_nodes.push_back(lca(nodes[i - 1], nodes[i]));
sort(unique_nodes.begin(), unique_nodes.end(), [](int a, int b) { return tin[a] < tin[b]; });
unique_nodes.erase(unique(unique_nodes.begin(), unique_nodes.end()), unique_nodes.end());
stack<int> stk;
stk.push(unique_nodes[0]);
for (int i = 1; i < (int)unique_nodes.size(); ++i) {
int u = unique_nodes[i];
while (!is_ancestor(stk.top(), u)) stk.pop();
int p = stk.top();
long long d = get_dist(u, p);
vtree[u].emplace_back(p, d);
vtree[p].emplace_back(u, d);
stk.push(u);
}
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
for (int i = 0; i < s; ++i) pq.emplace(0, X[i]);
long long res = INF;
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (dp[u] == 0) {
res = d;
break;
}
if (vis[u]) continue;
vis[u] = true;
for (auto &[v, w] : vtree[u]) pq.emplace(d + w, v);
}
for (int u : unique_nodes) {
vtree[u].clear();
vis[u] = false;
dp[u] = -1;
}
return res;
}
