#include<bits/stdc++.h>
using namespace std;
#include "factories.h"
struct weighted_graph{
long long N;
vector<vector<pair<long long,long long>>>adj, GC;
vector<long long>in, depth, crnci, dist, dp, sz;
vector<vector<long long>>lift;
inline void dec(long long _N){
N = _N;
adj.resize(N+1);
in.resize(N+1);
lift.resize(N+1);
depth.resize(N+1);
crnci.resize(N+1);
dist.resize(N+1);
GC.resize(N+1);
dp.resize(N+1);
sz.resize(N+1);
for (long long i = 1; i <= N; i++){
dp[i] = 0;
}
for (long long i = 1; i <= N; i++){
lift[i].resize(20);
}
}
inline void add_edge(long long A, long long B, long long D){
adj[A].push_back({B,D});
adj[B].push_back({A,D});
}
inline void init(){
long long timer = 1;
function<long long(long long,long long, long long h)>Dfs = [&](long long u, long long p, long long h){
in[u] = timer++;
depth[u] = depth[p] + 1;
sz[u] = 1;
dist[u] = h;
lift[u][0] = p;
for (auto& [x,w] : adj[u]){
if (x == p)continue;
sz[u] += Dfs(x,u, h + w);
}
return sz[u];
};
depth[1] = -1;
Dfs(1,1,0);
for (long long i = 1; i < 20; i++){
for (long long j = 1; j <= N; j++){
lift[j][i] = lift[lift[j][i-1]][i-1];
}
}
}
inline long long LCA(long long A, long long B){
if (depth[A] > depth[B])swap(A,B);
long long k = depth[B] - depth[A];
for (long long i = 19; i>=0; i--){
if ((1 << i) & k){
B = lift[B][i];
}
}
if (A == B)
return A;
for (long long i = 19; i>=0; i--){
if (lift[B][i] != lift[A][i]){
B = lift[B][i];
A = lift[A][i];
}
}
return lift[A][0];
}
inline long long Dijkstra(vector<long long>& sve){
priority_queue<pair<long long,long long>>pq;
for (long long i = 0; i < (long long)sve.size(); i++){
if (crnci[sve[i]] == 2){
pq.push({0,sve[i]});
}
}
while(!pq.empty()){
long long node = pq.top().second;
long long dst = -pq.top().first;
//cout << node << " " << dst << endl;
pq.pop();
if (crnci[node] == 1)return dst;
dp[node] = 1;
for (auto& [x,w] : GC[node]){
if (dp[x] == 0){
pq.push({-w-dst, x});
}
}
}
return -1;
}
inline long long Query(int S, int X[], int T, int Y[]){
vector<long long>sve;
for (long long i = 0; i < S; i++)X[i]++;
for (long long i = 0; i < T; i++)Y[i]++;
for (long long i = 0; i < S; i++){
sve.push_back(X[i]);
}
for (long long i = 0; i < T; i++){
sve.push_back(Y[i]);
}
sort(sve.begin(),sve.end(), [&](long long u, long long p){
return in[u] < in[p];
});
for (long long i = 1; i < S + T; i++){
sve.push_back(LCA(sve[i - 1], sve[i]));
}
sort(sve.begin(),sve.end(), [&](long long u, long long p){
return in[u] < in[p];
});
sve.erase(unique(sve.begin(),sve.end()), sve.end());
long long where = 0;
function<void()>build = [&](){
long long cp = sve[where];
where++;
long long max_ind = in[cp] + sz[cp] - 1;
while(where < sve.size() && in[sve[where]] <= max_ind){
GC[cp].push_back({sve[where], dist[sve[where]] - dist[cp]});
GC[sve[where]].push_back({cp,dist[sve[where]] - dist[cp]});
build();
}
};
build();
//for (long long i : sve)cout << " " << i;
// cout << endl;
for (long long i = 0; i < T; i++){
crnci[Y[i]] = 1;
}
for (long long i = 0; i < S; i++){
crnci[X[i]] = 2;
}
long long ans = Dijkstra(sve);
for (long long i = 0; i < T; i++){
crnci[Y[i]] = 0;
}
for (long long i = 0; i < S; i++){
crnci[X[i]] = 0;
}
for (long long i = 0; i < (long long)sve.size(); i++){
GC[sve[i]].clear();
dp[sve[i]] = 0;
}
return ans;
}
} G;
void Init(int N, int A[], int B[], int D[]) {
G.dec(N);
for (int i = 0; i < N - 1; i++){
G.add_edge(++A[i],++B[i],D[i]);
}
G.init();
}
long long Query(int S, int X[], int T, int Y[]) {
return G.Query(S,X,T,Y);
}
