// Author: Muhtasim Hossain Musanna (Musanna47 / mhmusanna)
#include "factories.h"
#include "bits/stdc++.h"
using namespace std;
#define nl "\n"
#define REPF(_i, _a, _b) for(int _i = _a; _i <= _b; _i++)
#define REPB(_i, _a, _b) for(int _i = _a; _i >= _b; _i--)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define X first
#define Y second
#define sza(_x) ((int)_x.size())
#define all(_x) _x.begin(), _x.end()
#define sort_des(_x) sort(all(_x), greater())
#define min_heap(_T, _pq, _cmp) auto _cmp = greater(); priority_queue<_T, vector<_T>, decltype(_cmp)> _pq(_cmp)
template<typename T1, typename T2>
using P = pair<T1, T2>;
template<typename T>
using V = vector<T>;
template<typename T>
using VV = V<V<T>>;
template<typename T>
using VVV = V<V<V<T>>>;
template<typename T>
using VVVV = V<V<V<V<T>>>>;
using S = string;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using pii = P<int, int>;
using pll = P<ll, ll>;
using vi = V<int>;
using vvi = VV<int>;
using vll = V<ll>;
using vvll = VV<ll>;
using vpii = V<pii>;
using vpll = V<pll>;
template<typename T>
void pout(T &a, string sep = " ", string fin = "\n") {
cout << a.first << sep << a.second << fin;
}
template<typename T>
void print(T &a, ll l, ll r, string sep = " ", string fin = "\n") {
for (ll i = l; i <= r; i++)
cout << a[i] << sep;
cout << fin;
}
template<typename T>
void printPairs(T &a, ll l, ll r, string fin = "\n") {
for (ll i = l; i <= r; i++)
pout(a[i]);
cout << fin;
}
template<typename T>
void printAll(T &a, string sep = " ", string fin = "\n") {
for (auto &ele: a)
cout << ele << sep;
cout << fin;
}
template<typename T>
void printPairsAll(T &a, string fin = "\n") {
for (auto &ele: a)
pout(ele);
cout << fin;
}
template<typename... Args>
void read(Args &... args) {
((cin >> args), ...);
}
template<typename... Args>
void out(Args... args) {
((cout << args << " "), ...);
}
template<typename... Args>
void outln(Args... args) {
((cout << args << " "), ...);
cout << nl;
}
template<typename T>
void vin(T &a, ll l, ll r) {
for (ll i = l; i <= r; i++)
cin >> a[i];
}
using bll = __int128;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll LL_INF = 1e18;
const double PI = 3.141592653589793;
const double EPS = 1e-12;
const int MAXN = 5e5 + 5;
const int H = 20;
vpii G[MAXN];
int subsize[MAXN];
bitset<MAXN> done;
multiset<ll> dists[MAXN];
int ancNode[MAXN][H + 1];
ll ancDist[MAXN][H + 1];
void getSubSize(int node, int par) {
subsize[node] = 1;
for (auto &[child, w]: G[node]) {
if (child != par && !done[child]) {
getSubSize(child, node);
subsize[node] += subsize[child];
}
}
}
void calc(int node, int par, int centroid, int h, ll dist) {
ancNode[node][h] = centroid;
ancDist[node][h] = dist;
for (auto &[child, w]: G[node]) {
if (child != par && !done[child]) {
calc(child, node, centroid, h, dist + w);
}
}
}
void centroidDecomp(int node = 1, int h = 0) {
// Get subtree sizes
getSubSize(node, -1);
// Get centroid
int centroid = node, par = -1;
while (true) {
bool stop = true;
for (auto &[child, w]: G[centroid]) {
if (child != par && !done[child]) {
if (subsize[child] > subsize[node] / 2) {
stop = false;
par = centroid, centroid = child;
break;
}
}
}
if (stop)
break;
}
// Mark centroid as done
done[centroid] = true;
// Perform task / query
calc(centroid, centroid, centroid, h, 0);
// Find next centroid
for (auto &[child, w]: G[centroid]) {
if (!done[child])
centroidDecomp(child, h + 1);
}
}
void update(int node, bool f) {
for (int h = 0; h <= H && ancNode[node][h]; h++) {
auto &par = ancNode[node][h];
auto &dist = ancDist[node][h];
if (f)
dists[par].emplace(dist);
else
dists[par].extract(dist);
}
}
ll query(int node) {
ll ret = LL_INF;
for (int h = 0; h <= H && ancNode[node][h]; h++) {
auto &par = ancNode[node][h];
auto &dist = ancDist[node][h];
if (!dists[par].empty())
ret = min(ret, dist + *dists[par].begin());
}
return ret;
}
void Init(int N, int A[], int B[], int D[]) {
for (int i = 0; i < N - 1; i++) {
G[A[i] + 1].emplace_back(B[i] + 1, D[i]);
G[B[i] + 1].emplace_back(A[i] + 1, D[i]);
}
centroidDecomp();
}
long long Query(int S, int X[], int T, int Y[]) {
for (int i = 0; i < S; i++)
update(X[i] + 1, true);
ll ans = LL_INF;
for (int i = 0; i < T; i++)
ans = min(ans, query(Y[i] + 1));
for (int i = 0; i < S; i++)
update(X[i] + 1, false);
return ans;
}
