#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define SZ 2234567
typedef long long ll;
int n,M=0,fst[SZ],vb[SZ],nxt[SZ]; ll vc[SZ];
void ad_de(int a,int b,ll c)
{
++M; nxt[M]=fst[a]; fst[a]=M;
vb[M]=b; vc[M]=c;
}
void adde(int a,int b,ll c)
{
ad_de(a,b,c); ad_de(b,a,c);
}
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
int dep[SZ],sz[SZ],so[SZ],fa[SZ]; ll dd[SZ];
void dfs1(int x,int fa=0)
{
sz[x]=1; dep[x]=dep[fa]+1; ::fa[x]=fa;
for esb(x,e,b) if(b!=fa)
{
dd[b]=dd[x]+vc[e];
dfs1(b,x),sz[x]+=sz[b];
if(sz[b]>sz[so[x]]) so[x]=b;
}
}
int top[SZ],dn[SZ],D,rv[SZ];
void dfs2(int x,int t,int fa=0)
{
top[x]=t; dn[x]=++D; rv[D]=x;
if(so[x]) dfs2(so[x],t,x);
for esb(x,e,b) if(b!=fa&&b!=so[x])
dfs2(b,b,x);
}
int lca(int a,int b)
{
while(top[a]!=top[b])
{
if(dep[top[a]]>dep[top[b]]) swap(a,b);
b=fa[top[b]];
}
if(dep[a]<dep[b]) return a;
return b;
}
ll dis(int a,int b)
{
return dd[a]+dd[b]-dd[lca(a,b)]*2;
}
void Init(int N, int A[], int B[], int D[]) {
n=N;
for(int i=0;i<n-1;++i)
adde(A[i]+1,B[i]+1,D[i]);
dfs1(1); dfs2(1,1);
}
typedef pair<int,int> pii;
pii p[SZ]; int pn;
#define fi first
#define se second
int st[SZ],sn,vs[SZ],vn,vfa[SZ],typ[SZ];
ll fd[SZ],fu[SZ];
void d1(int x,int fa=0)
{
fd[x]=4e18;
if(typ[x]==1) fd[x]=0;
for esb(x,e,b)
d1(b,x),fd[x]=min(fd[x],fd[b]+vc[e]);
}
#define pb push_back
#define mp make_pair
void d2(int x,int fa=0)
{
if(typ[x]==1) fu[x]=0;
{
vector<pair<ll,int>> tmp;
tmp.pb(mp(fu[x],0));
for esb(x,e,b)
tmp.pb(mp(fd[b]+vc[e],b));
sort(tmp.begin(),tmp.end());
for esb(x,e,b)
for(int j=0;j<2&&j<tmp.size();++j)
if(tmp[j].se!=b)
fu[b]=min(fu[b],tmp[j].fi+vc[e]);
}
for esb(x,e,b) if(b!=fa) d2(b,x);
}
ll gans(int r)
{
d1(r);
for(int i=1;i<=vn;++i) fu[vs[i]]=4e18;
d2(r);
// for(int i=1;i<=vn;++i)
// cout<<vs[i]<<":"<<fu[vs[i]]<<"w"<<fd[vs[i]]<<" "<<vfa[vs[i]]<<" "<<typ[vs[i]]<<"?\n";
ll ans=4e18;
for(int i=1;i<=vn;++i)
if(typ[vs[i]]==2)
ans=min(ans,min(fu[vs[i]],fd[vs[i]]));
return ans;
}
long long Query(int S, int X[], int T, int Y[]) {
pn=sn=vn=0;
for(int i=0;i<S;++i)
p[++pn]=pii(dn[X[i]+1],1);
for(int i=0;i<T;++i)
p[++pn]=pii(dn[Y[i]+1],2);
sort(p+1,p+1+pn);
for(int i=1;i<=pn;++i)
{
int x=rv[p[i].fi]; vs[++vn]=x;
if(!sn)
{
st[++sn]=x;
vfa[x]=0;
continue;
}
int g=lca(st[sn],x);
while(sn&&dep[st[sn]]>dep[g])
vfa[st[sn]]=g,--sn;
if(st[sn]!=g)
st[++sn]=g,
vfa[g]=st[sn-1],
vs[++vn]=g;
vfa[x]=st[sn];
st[++sn]=x;
}
M=0;
for(int i=1;i<=vn;++i)
fst[vs[i]]=typ[vs[i]]=0;
for(int i=1;i<=pn;++i)
typ[rv[p[i].fi]]=p[i].se;
int root=-1;
for(int i=1;i<=vn;++i)
if(vfa[vs[i]])
// cout<<vfa[vs[i]]<<"->"<<vs[i]<<"\n",
ad_de(vfa[vs[i]],vs[i],dd[vs[i]]-dd[vfa[vs[i]]]);
else root=vs[i];
// cout<<root<<"!\n";
return gans(root);
}
#ifdef LOCAL
#define D D__
#include "grader.cpp"
#endif
