#include "factories.h"
#include <cstdio>
#include <utility>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int,long long> ii;
vector<ii> al[500005];
long long w[500005],_w[500005];
int decomp[500005][20],r[500005];
bool target[500005];
priority_queue<ii, vector<ii>, greater<ii> > pq;
void dfs(int i){
for (vector<ii>::iterator it=al[i].begin();it!=al[i].end();it++){
if (w[(*it).first]==-1){
w[(*it).first]=w[i]+(*it).second;
r[(*it).first]=r[i]+1;
//2k decomp shit here
decomp[(*it).first][0]=i;
int x=i,y=0;
while (decomp[x][y]!=-1){
decomp[(*it).first][y+1]=decomp[x][y];
x=decomp[(*it).first][++y];
}
dfs((*it).first);
}
}
}
int move(int i,int j){
int k;
while (j!=0){
k=j&-j;
j-=k;
i=decomp[i][__builtin_ctz(k)];
}
return i;
}
int lca(int i,int j){
if (r[i]<r[j]) swap(i,j);
//i is now a lower or equal rank to j
//now we bring i up
i=move(i,r[i]-r[j]);
if (i==j) return i;
for (int x=19;x>=0;x--){
if (decomp[i][x]==-1 || decomp[i][x]==decomp[j][x]) continue;
i=decomp[i][x];
j=decomp[j][x];
}
return decomp[i][0];
}
long long dist(int i,int j){
return w[i]+w[j]-(w[lca(i,j)]<<1);
}
void Init(int N, int A[], int B[], int D[]) {
N--;
for (int x=0;x<N;x++){
al[A[x]].push_back(ii (B[x],D[x]));
al[B[x]].push_back(ii (A[x],D[x]));
}
memset(w,-1,sizeof(w));
memset(decomp,-1,sizeof(decomp));
w[0]=0;
dfs(0);
/*for (int x=0;x<=N;x++){
for (int y=0;y<=N;y++){
printf("%d ",dist(x,y));
}
printf("\n");
}*/
}
long long Query(int S, int X[], int T, int Y[]) {
if ((long long)S*(long long)T<10000){ //binary search on this number because im lazy
long long ans=1000000000000000000;
for (int x=0;x<S;x++){
for (int y=0;y<T;y++){
ans=min(ans,dist(X[x],Y[y]));
}
}
return ans;
}
else{
while (!pq.empty()) pq.pop();
memset(_w,-1,sizeof(_w));
memset(target,false,sizeof(target));
for (int x=0;x<T;x++){
target[Y[x]]=true;
}
for (int x=0;x<S;x++){
_w[X[x]]=0;
pq.push(ii(0,X[x]));
}
long long i,j;
while (true){
j=pq.top().first,i=pq.top().second,pq.pop();
if (target[i]) return j;
if (_w[i]<j) continue;
for (vector<ii>::iterator it=al[i].begin();it!=al[i].end();it++){
if (_w[(*it).first]==-1||_w[(*it).first]>_w[i]+(*it).second){
_w[(*it).first]=_w[i]+(*it).second;
pq.push(ii (_w[(*it).first],(*it).first));
}
}
}
}
}
