#include<bits/stdc++.h>
#include "factories.h"
#define fi first
#define se second
//#define int long long
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using aa = array<int,3>;
const int N = 5e5+5;
int n, m, u, v, x, root;
int sz[N];
long long res, c, dist[N];
bool num[N];
vector <pair<int,long long>> adj[N], anc[N];
void getSize(int u,int p){
sz[u] = 1;
for (pair<int, long long> it : adj[u]){
if (num[it.fi] || it.fi == p) continue;
getSize(it.fi,u);
sz[u] += sz[it.fi];
}
}
int getCentroid(int u,int p,int n){
for (pair<int, long long> it : adj[u]){
if (num[it.fi] || it.fi == p) continue;
if (sz[it.fi] * 2 > n) return getCentroid(it.fi,u,n);
}
return u;
}
void dfs(int u,int p,int root,long long length){
anc[u].push_back({root,length});
for (pair<int, long long> it : adj[u]){
if (num[it.fi] || it.fi == p) continue;
dfs(it.fi,u,root,length + it.se);
}
}
void decompose(int u){
getSize(u,0);
m = sz[u];
root = getCentroid(u,0,m);
num[root] = 1;
for (pair<int,long long> it : adj[root]){
if (num[it.fi]) continue;
dfs(it.fi,root,root,it.se);
}
for (pair<int,long long> it : adj[root]){
if (num[it.fi]) continue;
decompose(it.fi);
}
}
void update(int u,int type){
for (pair<int,long long> it : anc[u]){
if (type) dist[it.fi] = 1e18;
else dist[it.fi] = min(dist[it.fi],it.se);
}
}
void get(int u){
for (pair<int, long long> it : anc[u]){
res = min(res,dist[it.fi] + it.se);
}
}
void Init(int N, int A[], int B[], int D[]){
n = N;
for (int i = 0; i < n - 1; i++){
u = A[i] + 1;
v = B[i] + 1;
c = D[i];
adj[u].push_back({v,c});
adj[v].push_back({u,c});
}
for (int i = 1; i <= n; i++){
dist[i] = 1e18;
anc[i].push_back({i,0});
}
decompose(1);
}
long long Query(int S, int X[], int T, int Y[]){
res = 1e18;
for (int i = 0; i < S; i++) X[i]++;
for (int i = 0; i < T; i++) Y[i]++;
for (int i = 0; i < S; i++) update(X[i],0);
for (int i = 0; i < T; i++) get(Y[i]);
for (int i = 0; i < S; i++) update(X[i],1);
return res;
}
