#include <bits/stdc++.h>
using namespace std;
const int MN = 5e5+5, LG = 20;
typedef long long ll;
ll N, i, j, anc[MN][LG], st[MN], en[MN], t, a[MN], b[MN], d[MN], dep[MN], col[MN];
vector<ll> vec;
vector<pair<ll,ll>> adj[MN];
void dfs(int n,int p,int dp){
anc[n][0] = p; dep[n] = dp; st[n] = ++t;
for(auto v : adj[n]){
if(v.first==p) continue;
d[v.first] = d[n]+v.second;
dfs(v.first, n, dp+1);
}
en[n] = t;
}
void Init(int n,int *A,int *B,int *C){
N = n;
for(int i=0;i<n-1;i++){
adj[A[i]].push_back({B[i],C[i]});
adj[B[i]].push_back({A[i],C[i]});
}
dfs(0, -1, 1);
for(int j=1;j<LG;j++){
for(int i=0;i<N;i++){
if(anc[i][j-1]!=-1)
anc[i][j]=anc[anc[i][j-1]][j-1];
}
}
}
int lca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
for(int i=LG-1;i>=0;i--){
if((1<<i)<=dep[x]-dep[y])
x = anc[x][i];
}
if(x==y) return x;
for(int i=LG-1;i>=0;i--){
if(anc[x][i]!=anc[y][i]){
x = anc[x][i];
y = anc[y][i];
}
}
return anc[x][0];
}
bool cmp(int i,int j){return st[i]<st[j];}
ll Query(int S,int *X,int T,int *Y){
ll ans = 1LL<<60;
int *arr = (int*)malloc(sizeof(int)*(S+T));
for(int i=0;i<S;i++) arr[i]=X[i];
for(int i=0;i<T;i++) arr[i+S]=Y[i];
sort(arr,arr+S+T,cmp);
vec.clear();
for(i=0;i<S+T-1;i++)
vec.push_back(lca(arr[i],arr[i+1]));
for(i=0;i<S+T;i++)
vec.push_back(arr[i]);
sort(vec.begin(),vec.end(),cmp);
vec.erase(unique(vec.begin(),vec.end()),vec.end());
for(auto v : vec) col[v] = -1;
for(i=0;i<S;i++) col[X[i]]=0;
for(i=0;i<T;i++) col[Y[i]]=1;
stack<int> lst;
for(auto v : vec){
a[v] = b[v] = 1LL<<60;
if(col[v]==0) a[v] = 0;
else if(col[v]==1) b[v] = 0;
while(lst.size()&&en[lst.top()]<st[v]){
int n = lst.top();
ans = min(ans, a[n]+b[n]);
lst.pop();
if(lst.size()){
a[lst.top()]=min(a[lst.top()],a[n]+d[n]-d[lst.top()]);
b[lst.top()]=min(b[lst.top()],b[n]+d[n]-d[lst.top()]);
}
}
lst.push(v);
}
while(lst.size()){
int n = lst.top();
ans = min(ans, a[n]+b[n]);
lst.pop();
if(lst.size()){
a[lst.top()]=min(a[lst.top()],a[n]+d[n]-d[lst.top()]);
b[lst.top()]=min(b[lst.top()],b[n]+d[n]-d[lst.top()]);
}
}
return ans;
}
