#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl
using ll = long long;
const ll inf = 1e18;
const int maxn = 5e5 + 100;
const int LOG = 20;
int n;
vector<pair<ll,int>> g[maxn];
int par[LOG+1][maxn];
int dep[maxn];
ll len[maxn];
void dfs(int at, int p) {
for (int j=1; j<LOG; j++) {
par[j][at] = par[j-1][par[j-1][at]];
}
for (auto ed: g[at]) {
ll wei = ed.first;
int to = ed.second;
if (to == p) continue;
dep[to] = 1+dep[at];
len[to] = len[at] + wei;
par[0][to] = at;
dfs(to, at);
}
}
int lca(int u, int v) {
if (dep[u]<dep[v]) swap(u, v);
int dx = dep[u]-dep[v];
for (int j=0; j<LOG; j++) {
if (dx>>j&1) {
u = par[j][u];
}
}
if (u == v) return u;
for (int j=LOG-1; j>=0; j--) {
if (par[j][u] != par[j][v]) {
u = par[j][u];
v = par[j][v];
}
}
return par[0][u];
}
ll dist(int u, int v) {
int mid = lca(u, v);
return len[u] + len[v] - 2ll*len[mid];
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for (int i=0; i<n-1; i++) {
int u = A[i];
int v = B[i];
ll d = D[i];
g[u].push_back({d,v});
g[v].push_back({d,u});
}
dfs(0, -1);
}
long long Query(int S, int X[], int T, int Y[]) {
ll res = inf;
for (int i=0; i<S; i++) {
for (int j=0; j<T; j++) {
int u = X[i];
int v = Y[j];
res = min(res, dist(u, v));
}
}
return res;
}
int N, Q;
int A[maxn], B[maxn], D[maxn];
int S, T, X[maxn], Y[maxn];
