#include <bits/stdc++.h>
using namespace std;
vector<long long> d;
vector<int> dep;
vector<vector<pair<int, int>>> g;
vector<vector<int>> up;
int lg;
void dfs(int u) {
for (int i = 1; i < lg; i++) up[i][u] = up[i - 1][up[i - 1][u]];
for (auto [v, w] : g[u])
if (v ^ up[0][u])
d[v] = d[u] + w, dep[v] = dep[u] + 1, up[0][v] = u, dfs(v);
}
int lca(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
int k = dep[u] - dep[v];
for (int i = 0; i < lg; i++)
if (k >> i & 1)
u = up[i][u];
if (u == v) return u;
for (int i = lg - 1; i >= 0; i--)
if (up[i][u] ^ up[i][v])
u = up[i][u], v = up[i][v];
return up[0][u];
}
long long dist(int u, int v) {
return d[u] + d[v] - (d[lca(u, v)] << 1);
}
void Init(int n, int a[], int b[], int c[]) {
while ((1 << lg) <= n) ++lg;
g.resize(n), d.resize(n), dep.resize(n);
up = vector<vector<int>> (lg, vector<int> (n));
for (int i = 0; i < n - 1; i++) {
g[a[i]].push_back({b[i], c[i]});
g[b[i]].push_back({a[i], c[i]});
}
dfs(0);
}
long long Query(int s, int x[], int t, int y[]) {
long long ans = 1e18;
for (int i = 0; i < s; i++)
for (int j = 0; j < t; j++)
ans = min(ans, dist(x[i], y[j]));
return ans;
}
