# include "factories.h"
# include <bits/stdc++.h>
# define ll long long
# define vi vector<int>
# define pb push_back
# define pii pair<int, int>
# define fi first
# define se second
#pragma GCC optimize(03)
#pragma GCC target("avx2")
using namespace std;
ll n, a[500005], b[500005], d[500005], par[20][500005];
ll dist[500005], ans, dep[500005];
vector<pii> adj[500005];
void dfs(int x, int p) {
for(auto i : adj[x]) {
if(i.fi==p) continue;
par[0][i.fi]=x;
dep[i.fi]=dep[x]+1;
dist[i.fi]=dist[x]+i.se;
dfs(i.fi, x);
}
}
void build() {
for(int i=1; i<=19; i++ ){
for(int j=0; j<n; j++) {
par[i][j]=par[i-1][par[i-1][j]];
}
}
}
int lca(int a, int b) {
if(dep[a]>dep[b]) swap(a, b);
for(int i=19; i>=0; i--) {
if(dep[par[i][b]]>=dep[a]) {
b=par[i][b];
}
}
if(a==b) return a;
for(int i=19; i>=0; i--) {
if(par[i][a]!=par[i][b]) {
a=par[i][a];
b=par[i][b];
}
}
return par[0][a];
}
void Init(int N, int A[], int B[], int D[]) {
n=N;
for(int i=1; i<n; i++) a[i]=A[i-1], b[i]=B[i-1], d[i]=D[i-1];
for(int i=1; i<n; i++) {
adj[a[i]].pb({b[i], d[i]});
adj[b[i]].pb({a[i], d[i]});
}
par[0][0]=-1;
dfs(0, -1);
build();
}
long long Query(int S, int X[], int T, int Y[]) {
ans=1e14;
for(int i=0; i<S; i++) {
for(int j=0; j<T; j++) {
int tmp=lca(X[i], Y[j]);
// cout << "tmp " << X[i] << " " << Y[j] << " : " << tmp << endl;
ans=min(ans, (ll)dist[X[i]]+dist[Y[j]]-dist[tmp]*2LL);
}
}
return ans;
}
