#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
const int B = 3000;
vector<array<int, 2>>G[N];
int tin[N], TIME = 0;
long long d[N];
vector<long long>dEuler = {-1};
struct SparseTable{
vector<vector<long long>>sTable;
vector<int>LOG;
void init(){
int n = dEuler.size();
LOG.resize(n + 1);
LOG[1] = 0;
for(int i = 2;i <= n;++i){
LOG[i] = LOG[i >> 1] + 1;
}
sTable.resize(LOG[n] + 1);
for(int i = 0;i <= LOG[n];++i){
sTable[i].resize(n + 1);
}
for(int i = 1;i <= n;++i){
sTable[0][i] = dEuler[i];
}
for(int i = 1;i <= LOG[n];++i){
for(int j = 1;j + (1 << i) - 1 <= n;++j){
sTable[i][j] = min(sTable[i - 1][j], sTable[i - 1][j + (1 << (i - 1))]);
}
}
}
long long Query(int l, int r){
if(l > r)swap(l, r);
int lg = LOG[r - l + 1];
return min(sTable[lg][l], sTable[lg][r - (1 << lg) + 1]);
}
}table;
void dfs(int node, int par){
tin[node] = ++TIME;
dEuler.push_back(d[node]);
for(auto &[v, w] : G[node]){
if(v == par)continue;
d[v] = d[node] + w;
dfs(v, node);
dEuler.push_back(d[node]);
TIME++;
}
}
void Init(int N, int A[], int B[], int D[]){
for(int i = 0;i < N - 1;++i){
G[A[i]].push_back({B[i], D[i]});
G[B[i]].push_back({A[i], D[i]});
}
dfs(0, 0);
table.init();
}
long long Query(int S, int X[], int T, int Y[]){
long long mn = 1e18;
if(S >= B && T >= B){
vector<long long>dist2(N, 1e18);
priority_queue<array<long long, 2>>pq;
for(int i = 0;i < S;++i){
dist2[X[i]] = 0;
pq.push({dist2[X[i]], X[i]});
}
while(!pq.empty()){
long long d1 = -pq.top()[0], node = pq.top()[1];
pq.pop();
if(d1 != dist2[node])continue;
for(auto &[v, w] : G[node]){
if(dist2[v] > dist2[node] + w){
dist2[v] = dist2[node] + w;
pq.push({-dist2[v], v});
}
}
}
for(int i = 0;i < T;++i){
mn = min(mn, dist2[Y[i]]);
}
}
else{
for(int i = 0;i < S;++i){
for(int j = 0;j < T;++j){
mn = min(mn, d[X[i]] + d[Y[j]] - 2 * table.Query(tin[X[i]], tin[Y[j]]));
}
}
}
return mn;
}
// int main(){
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// int n, q;
// cin >> n >> q;
// int a[n - 1], b[n - 1], d[n - 1];
// for(int i = 0;i < n - 1;++i){
// cin >> a[i] >> b[i] >> d[i];
// }
// Init(n, a, b, d);
// while(q--){
// int s, t;
// cin >> s >> t;
// int x[s], y[t];
// for(int i = 0;i < s;++i){
// cin >> x[i];
// }
// for(int i = 0;i < t;++i){
// cin >> y[i];
// }
// cout << Query(s, x, t, y) << '\n';
// }
// }
