#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF = 1e9;
const ll MAXN = 5e5;
const ll MAXLog = log2(MAXN) + 1;
ll n, m;
vector<pair<ll, ll>> adj[MAXN+5];
ll depth[MAXN+5], distRoot[MAXN+5];
ll par[MAXLog+5][MAXN+5];
void dfs(ll cur){
for(ll i = 1; i <= MAXLog; i++) par[i][cur] = par[i-1][par[i-1][cur]];
for(auto [next, weight] : adj[cur]){
if(next == par[0][cur]) continue;
par[0][next] = cur;
depth[next] = depth[cur] + 1;
distRoot[next] = distRoot[cur] + weight;
dfs(next);
}
}
ll anc(ll cur, ll up){
for(ll i = 0; i <= MAXLog; i++){
if(up & (1 << i)) cur = par[i][cur];
}
return cur;
}
ll lca(ll a, ll b){
if(depth[a] > depth[b]) swap(a, b);
b = anc(b, depth[b] - depth[a]);
if(a == b) return a;
for(ll i = MAXLog; i >= 0; i--){
if(par[i][a] == par[i][b]) continue;
a = par[i][a];
b = par[i][b];
}
return par[0][a];
}
ll dist(ll a, ll b){
ll ret = distRoot[a] + distRoot[b] - (2 * distRoot[lca(a, b)]);
return ret;
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for(ll i = 1; i <= n-1; i++){
ll u = A[i-1] + 1, v = B[i-1] + 1, w = D[i-1];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
depth[1] = 1;
dfs(1);
}
long long Query(int S, int X[], int T, int Y[]) {
ll ans = INF;
for(ll i = 0; i < S; i++){
for(ll j = 0; j < T; j++){
ll u = X[i] + 1, v = Y[j] + 1;
// cerr << u << ' ' << v << " : " << dist(u, v) << endl;
ans = min(dist(u, v), ans);
}
}
return ans;
}
