// 🌲🌲🌲🌲🌲🌳🌳🌳🌳🌳🌳🌴🌴🌴🌴🌴🌴🌴🌴
#include <bits/stdc++.h>
bool M1;
#include "factories.h"
#define FOR(i, a, b) for (long long i = (a), _b = (b); i <= _b; ++i)
#define REV(i, a, b) for (long long i = (a), _b = (b); i >= _b; --i)
using namespace std;
#define MAXN 500005
#define MAXQ 100005
long long n, q;
vector<pair<long long, long long>> g[MAXN];
bool blocked[MAXN];
long long sz[MAXN];
long long par[MAXN];
long long sumWeight[MAXN];
long long bestVal[MAXN];
const long long INF = 1e15;
int FirstCentroid = 0;
///++++++++++++++++++++++++++++++++++++++///
void minimize(long long &a, const long long &b) {
if (a > b) a = b;
}
void preCalc(long long u, long long p) {
for (pair<long long, long long> &x : g[u]) {
long long v, w; tie(v, w) = x;
if (v == p) continue;
sumWeight[v] = sumWeight[u] + w;
preCalc(v, u);
}
}
long long dist(long long a, long long b) {
return sumWeight[b] - sumWeight[a];
}
void calc(long long u, long long p) {
sz[u] = 1;
for (pair<long long, long long> &x : g[u]) {
long long v, w; tie(v, w) = x;
if (blocked[v] || v == p) continue;
calc(v, u);
sz[u] += sz[v];
}
}
long long FindCentroid(long long u, long long p, long long SZ) {
for (pair<long long, long long> &x : g[u]) {
long long v, w; tie(v, w) = x;
if (blocked[v] || v == p) continue;
if (sz[v] > SZ) return FindCentroid(v, u, SZ);
}
return u;
}
void decompose(long long curNode, long long preCentroid) {
calc(curNode, 0);
long long c = FindCentroid(curNode, 0, sz[curNode] / 2);
if (FirstCentroid == 0) FirstCentroid = c;
par[c] = preCentroid;
blocked[c] = true;
for (pair<long long, long long> &x : g[c]) {
long long v, w; tie(v, w) = x;
if (blocked[v]) continue;
decompose(v, c);
}
}
void update(long long curNode) {
long long fixed = curNode;
while (curNode != 0) {
minimize(bestVal[curNode], dist(curNode, fixed));
curNode = par[curNode];
}
}
void reset(long long curNode) {
long long fixed = curNode;
while (curNode != 0) {
bestVal[curNode] = 1e15;
curNode = par[curNode];
}
}
long long query(long long curNode) {
long long fixed = curNode;
long long res = INF;
while (curNode != 0) {
minimize(res, bestVal[curNode] + dist(curNode, fixed));
curNode = par[curNode];
}
return res;
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
FOR(i, 1, n - 1){
long long u = A[i - 1];
long long v = B[i - 1];
long long w = D[i - 1];
u++;
v++;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
decompose(1, 0);
preCalc(FirstCentroid, 0);
FOR(i, 1, n) bestVal[i] = 1e15;
}
long long Query(int S, int X[], int T, int Y[]) {
vector<long long> tmpNode;
FOR(i, 1, S) {
long long curNode = X[i - 1];
curNode++;
update(curNode);
tmpNode.push_back(curNode);
}
long long res = INF;
FOR(i, 1, T) {
long long curNode = Y[i - 1];
curNode++;
minimize(res, query(curNode));
}
for (long long &curNode : tmpNode) reset(curNode);
return res;
}
//void solve() {
// cin >> n >> q;
// FOR(i, 1, n - 1) {
// long long u, v, w; cin >> u >> v >> w;
// u++; v++;
// g[u].push_back({v, w});
// g[v].push_back({u, w});
// }
// decompose(1, 0);
// preCalc(FirstCentroid, 0);
// FOR(i, 1, n) bestVal[i] = 1e15;
// FOR(Nium, 1, q) {
// long long S, T; cin >> S >> T;
// vector<long long> tmpNode;
// FOR(i, 1, S) {
// long long curNode; cin >> curNode;
// curNode++;
// update(curNode);
// tmpNode.push_back(curNode);
// }
// long long res = INF;
// FOR(i, 1, T) {
// long long curNode; cin >> curNode;
// curNode++;
// minimize(res, query(curNode));
// }
// for (long long &curNode : tmpNode) reset(curNode);
// cout << res << '\n';
// }
//}
//
//++++++++++++++++++++++++++++++++++++++///
//
//#define task "test"
//int32_t main() {
// if (fopen(task".inp","r")) {
// freopen(task".inp","r",stdin);
// freopen(task".out","w",stdout);
// }
// ios_base::sync_with_stdio(false);
// cin.tie(nullptr); cout.tie(nullptr);
// solve();
// bool M2;
// cerr << "++++++++++++++++++++++++++++\n";
// cerr << "Time: " << clock() << "ms" << '\n';
// cerr << "Memory: " << abs(&M2 - &M1) / 1024 / 1024 << "MB" << '\n';
// cerr << "++++++++++++++++++++++++++++\n";
// return 0;
//}
