#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e5 + 10;
int sz[maxn], cpar[maxn], h[maxn], par[maxn][21];
ll dis[maxn], dp[maxn];
bool mark[maxn];
vector<pair<int, int> > t[maxn];
int lca(int v, int u){
if (h[v] < h[u])
swap(v, u);
for (int i = 19; i >= 0; i--)
if (h[v] - (1 << i) >= h[u])
v = par[v][i];
if (v == u)
return v;
for (int i = 19; i >= 0; i--)
if (par[v][i] != par[u][i])
v = par[v][i], u = par[u][i];
return par[v][0];
}
ll distance(int v, int u){
return dis[v] + dis[u] - 2ll * dis[lca(v, u)];
}
int dfs_sz(int v, int p = -1){
sz[v] = 1;
for (auto edge : t[v]){
int u = edge.first;
if (u != p and mark[u] == false)
sz[v] += dfs_sz(u, v);
}
return sz[v];
}
void centroid_decomposition(int v, int centpar = -1){
dfs_sz(v);
int parent = -1, Mx = sz[v];
bool flag = 1;
while (flag){
flag = 0;
for (auto edge : t[v]){
int u = edge.first;
if (u != parent and mark[u] == false and sz[u] > Mx / 2){
parent = v;
v = u;
flag = 1;
break;
}
}
}
cpar[v] = centpar;
mark[v] = true;
for (auto u : t[v])
if (mark[u.first] == false)
centroid_decomposition(u.first, v);
}
void dfs(int v, int p = -1){
par[v][0] = p;
for (int i = 1; par[v][i - 1] != -1 and i <= 19; i++)
par[v][i] = par[par[v][i - 1]][i - 1];
for (auto edge : t[v]){
int u = edge.first, w = edge.second;
if (u != p){
h[u] = h[v] + 1;
dis[u] = dis[v] + w;
dfs(u, v);
}
}
}
void Init(int N, int A[], int B[], int D[]){
for (int i = 0; i < N - 1; i++){
int v = A[i], u = B[i], w = D[i];
t[v].push_back({u, w});
t[u].push_back({v, w});
}
memset(par, -1, sizeof par);
dfs(0);
centroid_decomposition(0);
memset(dp, 63, sizeof dp);
}
long long Query(int S, int X[], int T, int Y[]){
for (int i = 0; i < S; i++){
int v = X[i];
while (v != -1){
dp[v] = min(dp[v], distance(v, X[i]));
v = cpar[v];
}
}
ll answer = 1e18;
for (int i = 0; i < T; i++){
int v = Y[i];
while (v != -1){
answer = min(answer, dp[v] + distance(v, Y[i]));
v = cpar[v];
}
}
for (int i = 0; i < S; i++){
int v = X[i];
while (v != -1){
dp[v] = 1e18;
v = cpar[v];
}
}
return answer;
}
