#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
i64 n,q,dist[500009],mindist[500009];
int _t=0,tin[500009],tout[500009],par[20][500009];
vector<pair<int,i64>> adj[500009],bdj[500009];
void DFS(int u,int pu,i64 d)
{
tin[u]=++_t; dist[u]=d; par[0][u]=pu;
for(auto& v:adj[u])
if(v.first!=pu) DFS(v.first,u,d+v.second);
tout[u]=_t;
}
bool isA(int u,int v) {return tin[u]<=tin[v] and tout[v]<=tout[u];}
int LCA(int u,int v)
{
if(isA(u,v)) return u;
if(isA(v,u)) return v;
for(int i=19;i>=0;--i)
if(!isA(par[i][u],v)) u=par[i][u];
return par[0][u];
}
//i64 dist2(int u,int v) {return dist[u]+dist[v]-2*dist[LCA(u,v)];}
void Init(int N,int A[],int B[],int D[])
{
n=N;
for(int i=0;i<n-1;++i)
{
++A[i]; ++B[i];
adj[A[i]].push_back({B[i],D[i]});
adj[B[i]].push_back({A[i],D[i]});
}
DFS(1,0,0); par[0][1]=1;
for(int i=1;i<20;++i) for(int j=1;j<=n;++j)
par[i][j]=par[i-1][par[i-1][j]];
}
i64 Query(int S,int X[],int T,int Y[])
{
i64 res=9e18;
vector<int> Z(S+T);
for(int i=0;i<S;++i) Z[i]=++X[i];
for(int i=0;i<T;++i) Z[i+S]=++Y[i];
sort(Z.begin(),Z.end(),[&](int x,int y){return tin[x]<tin[y];});
for(int i=1;i<S+T;++i) Z.push_back(LCA(Z[i],Z[i-1]));
sort(Z.begin(),Z.end(),[&](int x,int y){return tin[x]<tin[y];});
Z.resize(distance(Z.begin(),unique(Z.begin(),Z.end())));
stack<int> st; st.push(Z[0]); mindist[Z[0]]=3e18;
for(int i=1;i<Z.size();++i)
{
while(!isA(st.top(),Z[i])) st.pop();
bdj[st.top()].push_back({Z[i],dist[Z[i]]-dist[st.top()]});
bdj[Z[i]].push_back({st.top(),dist[Z[i]]-dist[st.top()]});
st.push(Z[i]); mindist[Z[i]]=3e18;
}
set<pair<i64,int>> dij;
for(int i=0;i<S;++i)
{
mindist[X[i]]=0;
dij.insert({0,X[i]});
}
while(!dij.empty())
{
int u=dij.begin()->second;
dij.erase(dij.begin());
for(auto& v:bdj[u])
{
if(mindist[v.first]>mindist[u]+v.second)
{
dij.erase({mindist[v.first],v.first});
mindist[v.first]=mindist[u]+v.second;
dij.insert({mindist[v.first],v.first});
}
}
}
for(int i=0;i<T;++i) res=min(res,mindist[Y[i]]);
for(int i=0;i<Z.size();++i) bdj[Z[i]].clear();
return res;
}
// No Raven here :((, cuz size limit exceeded
