#include <bits/stdc++.h>
//#define int long long
#define fi first
#define se second
#define name "a"
using namespace std;
using ii = pair<long long,long long>;
using aa = array<int,3>;
const int N=1e6+5;
vector<ii> adj[N];
int in[N],out[N];
int timer=0;
long long h[N],d[N];
int up[N][19];
bool cmp(int a,int b) {
return in[a]<in[b];
}
void dfs(int u,int p) {
in[u]=++timer;
up[u][0]=p;
for(int i=1;i<=18;i++) {
up[u][i]=up[up[u][i-1]][i-1];
}
for(ii v:adj[u]) {
if(v.fi==p) continue;
h[v.fi]=h[u]+v.se;
dfs(v.fi,u);
}
out[u]=timer;
}
bool inside(int u,int v) {
return(u==0 || (in[u]<=in[v] && out[v]<=out[u]));
}
int lca(int u,int v) {
if(inside(u,v)) return u;
if(inside(v,u)) return v;
for(int i=18;i>=0;i--) {
if(!inside(up[u][i],v)) {
u=up[u][i];
}
}
return up[u][0];
}
int mp[N];
vector<ii> g[N];
void Init(int N, int A[], int B[], int D[]) {
int n = N;
for (int i = 0; i < N - 1; i++){
int u = A[i] + 1;
int v = B[i] + 1;
int c = D[i];
adj[u].push_back({v,c});
adj[v].push_back({u,c});
}
dfs(1,0);
}
long long Query(int S, int X[], int T, int Y[]) {
int n=S,m=T;
vector<int> a,b,c;
for(int i=0;i<n;i++) {
int u=X[i]+1;
a.push_back(u);
c.push_back(u);
}
for(int i=0;i<m;i++) {
int u=Y[i]+1;
b.push_back(u);
c.push_back(u);
}
for(int x:c) mp[x]=1;
sort(c.begin(),c.end(),cmp);
for(int i=1;i<a.size()+b.size();i++) {
int x=lca(c[i],c[i-1]);
if(!mp[x]) c.push_back(x);
mp[x]=1;
}
sort(c.begin(),c.end(),cmp);
stack<int> st;
for(int x:c) {
g[x].clear();
d[x]=1e18;
mp[x]=0;
}
for(int u:c) {
while(!st.empty() && !inside(st.top(),u)) st.pop();
if(!st.empty()) {
g[st.top()].push_back({u,-h[st.top()]+h[u]});
g[u].push_back({st.top(),-h[st.top()]+h[u]});
//cout << u << ' ' << st.top() << endl;
}
st.push(u);
}
priority_queue<ii,vector<ii>,greater<ii>> q;
for(int x:a) {
d[x]=0;
q.push({0,x});
}
while(!q.empty()) {
ii u=q.top();
q.pop();
if(u.fi > d[u.se]) continue;
for(ii v:g[u.se]) {
if(d[v.fi]>u.fi+v.se) {
q.push({d[v.fi]=u.fi+v.se,v.fi});
}
}
}
long long res=363636363636363636;
for(int u:b) {
res=min(res,d[u]);
}
//cout << res << '\n';
return res;
}
