#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
const long long INF = 1000000000000000;
struct heavy_light_decomposition{
vector<int> p, sz, in, next;
vector<long long> d;
heavy_light_decomposition(){
}
heavy_light_decomposition(vector<int> &p, vector<vector<int>> &c, vector<long long> &d): p(p), d(d){
int N = p.size();
sz = vector<int>(N, 1);
dfs1(c);
in = vector<int>(N);
next = vector<int>(N, 0);
int t = 0;
dfs2(c, t);
}
void dfs1(vector<vector<int>> &c, int v = 0){
for (int &w : c[v]){
dfs1(c, w);
sz[v] += sz[w];
if (sz[w] > sz[c[v][0]]){
swap(w, c[v][0]);
}
}
}
void dfs2(vector<vector<int>> &c, int &t, int v = 0){
in[v] = t;
t++;
for (int w : c[v]){
if (w == c[v][0]){
next[w] = next[v];
} else {
next[w] = w;
}
dfs2(c, t, w);
}
}
int lca(int u, int v){
while (true){
if (in[u] > in[v]){
swap(u, v);
}
if (next[u] == next[v]){
return u;
}
v = p[next[v]];
}
}
long long dist(int u, int v){
return d[u] + d[v] - 2 * d[lca(u, v)];
}
};
heavy_light_decomposition HLD;
vector<vector<pair<long long, int>>> E2;
vector<long long> d2;
void Init(int N, int A[], int B[], int D[]){
vector<vector<pair<int, int>>> E(N);
for (int i = 0; i < N - 1; i++){
E[A[i]].push_back(make_pair(D[i], B[i]));
E[B[i]].push_back(make_pair(D[i], A[i]));
}
vector<int> p(N, -1);
vector<vector<int>> c(N);
vector<long long> d(N, 0);
queue<int> Q;
Q.push(0);
while (!Q.empty()){
int v = Q.front();
Q.pop();
for (auto P : E[v]){
int w = P.second;
if (w != p[v]){
p[w] = v;
c[v].push_back(w);
d[w] = d[v] + P.first;
Q.push(w);
}
}
}
HLD = heavy_light_decomposition(p, c, d);
E2.resize(N);
d2 = vector<long long>(N, -1);
}
long long Query(int S, int X[], int T, int Y[]){
vector<pair<int, int>> V;
for (int i = 0; i < S; i++){
V.push_back(make_pair(HLD.in[X[i]], X[i]));
}
for (int i = 0; i < T; i++){
V.push_back(make_pair(HLD.in[Y[i]], Y[i]));
}
sort(V.begin(), V.end());
stack<int> st;
st.push(V[0].second);
for (int i = 1; i < S + T; i++){
int v = HLD.lca(V[i - 1].second, V[i].second);
while (!st.empty()){
int w = st.top();
if (HLD.d[v] < HLD.d[w]){
st.pop();
int pr = v;
if (!st.empty()){
if (HLD.d[pr] < HLD.d[st.top()]){
pr = st.top();
}
}
if (pr != w){
long long D = HLD.d[w] - HLD.d[pr];
E2[pr].push_back(make_pair(D, w));
E2[w].push_back(make_pair(D, pr));
}
} else {
break;
}
}
if (st.empty()){
st.push(v);
} else if (st.top() != v){
st.push(v);
}
if (st.top() != V[i].second){
st.push(V[i].second);
}
}
while (st.size() >= 2){
int v = st.top();
st.pop();
int w = st.top();
long long D = HLD.d[v] - HLD.d[w];
E2[v].push_back(make_pair(D, w));
E2[w].push_back(make_pair(D, v));
}
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]));
}
vector<int> s;
while (!pq.empty()){
long long c = pq.top().first;
int v = pq.top().second;
pq.pop();
if (d2[v] == -1){
d2[v] = c;
s.push_back(v);
for (auto P : E2[v]){
int w = P.second;
if (d2[w] == -1){
pq.push(make_pair(c + P.first, w));
}
}
}
}
long long ans = INF;
for (int i = 0; i < T; i++){
ans = min(ans, d2[Y[i]]);
}
int cnt = s.size();
for (int i = 0; i < cnt; i++){
E2[s[i]].clear();
d2[s[i]] = -1;
}
return ans;
}
