#undef _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define fi first
#define si second
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef tuple<int,int,int> ti;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll = long long;
#include "factories.h"
const int MAXN = 500010, LOG = 20;
const ll INF = 1e18;
int n;
vector<pi> g[MAXN];
int tk[MAXN][LOG];
int dep[MAXN];
ll wd[MAXN];
int vis[MAXN];
ll close[MAXN];
struct CentroidDecomposition {
vector<int> sub;
vector<int> rem;
vector<int> tree;
void init(int nodes) {
sub.resize(nodes + 1);
rem.resize(nodes + 1);
tree.resize(nodes + 1, -1);
build(1, -1);
}
int dfs(int u, int p) {
sub[u] = 1;
for (auto i: g[u]) {
if (i.fi == p || rem[i.fi])
continue;
sub[u] += dfs(i.fi, u);
}
return sub[u];
}
int cent(int u, int sz, int p) {
for (auto i: g[u]) {
if (i.fi == p || rem[i.fi])
continue;
if (sub[i.fi] * 2 <= sz)
continue;
return cent(i.fi, sz, u);
}
return u;
}
void build(int u, int p) {
int c = cent(u, dfs(u, -1), -1);
rem[c] = 1;
tree[c] = p;
// debug(c - 1, p - 1);
for (auto i: g[c]) {
if (rem[i.fi])
continue;
build(i.fi, c);
}
}
int get(int u) {
return tree[u];
}
} cd;
void dfs(int x, int pa) {
dep[x] = dep[pa] + 1;
vis[x] = 1;
tk[x][0] = pa;
for (int i = 1; i < LOG; ++i) {
if (tk[x][i - 1] == -1)
continue;
tk[x][i] = tk[tk[x][i - 1]][i - 1];
}
for (auto i: g[x]) {
if (i.fi == pa || vis[i.fi])
continue;
wd[i.fi] = wd[x] + i.si;
dfs(i.fi, x);
}
}
int jump(int x, int d) {
for (int i = 0; i < LOG; ++i) {
if (x == -1)
return -1;
if (d & (1 << i))
x = tk[x][i];
}
return x;
}
int lca(int x, int y) {
if (dep[x] < dep[y]) // wlog x is further from root
swap(x, y);
x = jump(x, dep[x] - dep[y]);
if (x == y)
return x;
for (int i = LOG - 1; i >= 0; --i) {
int nx = tk[x][i], ny = tk[y][i];
if (nx == -1 || ny == -1)
continue;
if (nx != ny)
x = nx, y = ny;
}
return tk[x][0];
}
ll dist(int x, int y) {
return wd[x] + wd[y] - 2 * wd[lca(x, y)];
}
void Init(int _N, int _A[], int _B[], int _D[]) {
n = _N;
for (int i = 0; i < n - 1; ++i) {
int u = _A[i], v = _B[i], c = _D[i];
// ++u, ++v;
g[u].pb({v, c});
g[v].pb({u, c});
}
memset(tk, -1, sizeof tk);
dfs(0, -1);
cd.init(n + 1);
}
void update(int x) {
int cur = x;
while (1) {
if (cur == -1)
break;
close[cur] = min(close[cur], dist(cur, x));
cur = cd.get(cur);
}
}
ll query(int x) {
int cur = x;
ll ret = INF;
while (1) {
if (cur == -1)
break;
ret = min(ret, close[cur] + dist(cur, x));
cur = cd.get(cur);
}
return ret;
}
long long Query(int _S, int _X[], int _T, int _Y[]) {
for (int i = 0; i <= n; ++i)
close[i] = INF;
for (int i = 0; i < _S; ++i) {
int node = _X[i];
update(node);
}
ll ans = INF;
for (int i = 0; i < _T; ++i) {
int node = _Y[i];
ans = min(ans, query(node));
}
return ans;
}
