#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
const int max_n = 500005;
const int log_n = 20;
const long long inf = 1e18;
vector<pair<int, int>> adj[max_n];
vector<pair<long long, long long>> tree[max_n];
int up[max_n][log_n];
int depth[max_n];
long long dist[max_n];
long long tin[max_n], tout[max_n], timer = 0;
long long dp[max_n];
bool visited[max_n];
void dfs(int u, int parent) {
up[u][0] = parent;
for (int i = 1; i < log_n; i++) {
up[u][i] = up[up[u][i - 1]][i - 1];
}
tin[u] = ++timer;
for (int i = 0; i < (int)adj[u].size(); i++) {
int to = adj[u][i].first;
int w = adj[u][i].second;
if (to != parent) {
depth[to] = depth[u] + 1;
dist[to] = dist[u] + w;
dfs(to, u);
}
}
tout[u] = timer;
}
int lca(int u, int v) {
if (depth[u] < depth[v]) {
int temp = u;
u = v;
v = temp;
}
for (int i = log_n - 1; i >= 0; i--) {
if (up[u][i] != -1 && depth[up[u][i]] >= depth[v]) {
u = up[u][i];
}
}
if (u == v) return u;
for (int i = log_n - 1; i >= 0; i--) {
if (up[u][i] != -1 && 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 cmp(int a, int b) {
return tin[a] < tin[b];
}
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]].push_back(make_pair(b[i], d[i]));
adj[b[i]].push_back(make_pair(a[i], d[i]));
}
for (int i = 0; i < log_n; i++) up[0][i] = 0;
depth[0] = 0;
dist[0] = 0;
dfs(0, 0);
for (int i = 0; i < n; i++) dp[i] = -1;
}
long long Query(int s, int x[], int t, int y[]) {
vector<int> spec;
for (int i = 0; i < s; i++) spec.push_back(x[i]);
for (int i = 0; i < t; i++) {
spec.push_back(y[i]);
dp[y[i]] = 0;
}
sort(spec.begin(), spec.end(), cmp);
vector<int> nodes = spec;
for (int i = 1; i < (int)spec.size(); i++) {
nodes.push_back(lca(spec[i - 1], spec[i]));
}
sort(nodes.begin(), nodes.end(), cmp);
nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());
stack<int> st;
st.push(nodes[0]);
for (int i = 1; i < (int)nodes.size(); i++) {
int u = nodes[i];
while (!is_ancestor(st.top(), u)) st.pop();
int v = st.top();
long long d = get_dist(u, v);
tree[u].push_back(make_pair(v, d));
tree[v].push_back(make_pair(u, d));
st.push(u);
}
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
for (int i = 0; i < s; i++) {
pq.push(make_pair(0, x[i]));
}
long long res = inf;
while (!pq.empty()) {
pair<long long, int> top = pq.top(); pq.pop();
long long d = top.first;
int u = top.second;
if (dp[u] == 0) {
res = d;
break;
}
if (visited[u]) continue;
visited[u] = true;
for (int i = 0; i < (int)tree[u].size(); i++) {
int to = tree[u][i].first;
long long w = tree[u][i].second;
pq.push(make_pair(d + w, to));
}
}
for (int i = 0; i < (int)nodes.size(); i++) {
int u = nodes[i];
tree[u].clear();
visited[u] = false;
dp[u] = -1;
}
return res;
}
