#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
long long par[20][500005], dist[500005], depth[500005], mp[500005], exist[500005], d[500005], cnt, sz;
vector<pair<long long, long long> > adj[500005];
priority_queue<pair<long long, long long> > pq;
vector<long long> vec, vec2, vec3;
bool visited[500005];
long long lca(long long u, long long v)
{
if (depth[u]>depth[v])
swap(u, v);
long long cur=depth[v]-depth[u];
for (long long i=19; i>=0; i--)
if (cur&(1<<i))
v=par[i][v];
if (u==v)
return u;
for (long long i=19; i>=0; i--)
{
if (par[i][u]!=par[i][v])
{
u=par[i][u];
v=par[i][v];
}
}
return par[0][u];
}
void dfs(long long u, long long p, long long dis, long long dep)
{
mp[u]=cnt;
cnt++;
par[0][mp[u]]=mp[p];
dist[mp[u]]=dis;
depth[mp[u]]=dep;
for (long long i=0; i<adj[u].size(); i++)
{
long long v=adj[u][i].first, w=adj[u][i].second;
if (v!=p)
dfs(v, u, dis+w, dep+1);
}
}
void dfs2(long long ind)
{
long long u=vec3[ind];
while (cnt<sz && lca(u, vec3[cnt])==u)
{
long long v=vec3[cnt];
long long w=dist[v]-dist[u];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
cnt++;
dfs2(cnt-1);
}
}
void Init(int N, int A[], int B[], int D[])
{
for (long long i=0; i<=N-2; i++)
{
adj[A[i]].push_back({B[i], D[i]});
adj[B[i]].push_back({A[i], D[i]});
}
dfs(0, 0, 0, 0);
for (long long i=1; i<=19; i++)
for (long long j=0; j<N; j++)
par[i][j]=par[i-1][par[i-1][j]];
for (long long i=0; i<N; i++)
adj[i].clear();
}
long long Query(int S, int X[], int T, int Y[])
{
// cout << "Query\n";
vec.clear();
vec2.clear();
vec3.clear();
for (long long i=0; i<S; i++)
{
X[i]=mp[X[i]];
vec.push_back(X[i]);
}
for (long long i=0; i<T; i++)
{
Y[i]=mp[Y[i]];
vec.push_back(Y[i]);
}
sort(vec.begin(), vec.end());
for (long long i=0; i<=vec.size()-2; i++)
{
vec2.push_back(lca(vec[i], vec[i+1]));
exist[vec2[i]]=i+1;
}
for (long long i=0; i<=vec.size()-2; i++)
{
if (!exist[vec[i]])
{
vec3.push_back(vec[i]);
vec3.push_back(vec2[i]);
}
else if (exist[vec[i]]==i+1)
vec3.push_back(vec[i]);
}
vec3.push_back(vec[vec.size()-1]);
sort(vec3.begin(), vec3.end());
for (long long i=0; i<vec2.size(); i++)
exist[vec2[i]]=0;
/* cout << "vec: ";
for (long long i=0; i<vec.size(); i++)
cout << vec[i] << ' ';
cout << '\n';
cout << "vec2: ";
for (long long i=0; i<vec2.size(); i++)
cout << vec2[i] << ' ';
cout << '\n';
cout << "vec3: ";
for (long long i=0; i<vec3.size(); i++)
cout << vec3[i] << ' ';
cout << '\n'; */
sz=vec3.size();
cnt=1;
dfs2(0);
/* for (long long i=0; i<vec3.size(); i++)
{
cout << "adj " << vec3[i] << ": ";
for (long long j=0; j<adj[vec3[i]].size(); j++)
cout << adj[vec3[i]][j].first << ' ';
cout << '\n';
} */
for (long long i=0; i<sz; i++)
{
d[vec3[i]]=1e18;
visited[vec3[i]]=0;
}
for (long long i=0; i<S; i++)
{
d[X[i]]=0;
pq.push({0, X[i]});
}
while (!pq.empty())
{
long long u=pq.top().second;
pq.pop();
if (visited[u])
continue;
visited[u]=1;
for (long long i=0; i<adj[u].size(); i++)
{
long long v=adj[u][i].first, w=adj[u][i].second;
if (d[v]>d[u]+w)
{
d[v]=d[u]+w;
pq.push({-d[v], v});
}
}
}
long long ans=1e18;
for (long long i=0; i<T; i++)
ans=min(ans, d[Y[i]]);
for (long long i=0; i<sz; i++)
adj[vec3[i]].clear();
return ans;
}
