// 🌲🌲🌲🌲🌲🌳🌳🌳🌳🌳🌳🌴🌴🌴🌴🌴🌴🌴🌴
#include <bits/stdc++.h>
bool M1;
#define int long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define REV(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
using namespace std;
#define MAXN 500005
#define MAXQ 100005
int n, q;
vector<pair<int, int>> g[MAXN];
bool blocked[MAXN];
int sz[MAXN];
int par[MAXN];
int dep[MAXN];
int sumWeight[MAXN];
int curWeight[MAXN];
int up[MAXN][20];
int bestVal[MAXN];
const int INF = 1e15;
///++++++++++++++++++++++++++++++++++++++///
void minimize(int &a, const int &b) {
if (a > b) a = b;
}
void preCalc(int u, int p) {
for (pair<int, int> &x : g[u]) {
int v, w; tie(v, w) = x;
if (v == p) continue;
up[v][0] = u;
dep[v] = dep[u] + 1;
sumWeight[v] = sumWeight[u] + w;
curWeight[v] = w;
preCalc(v, u);
}
}
void prepareLCA() {
FOR(j, 1, 19) FOR(i, 1, n) {
up[i][j] = up[up[i][j - 1]][j - 1];
}
}
int LCA(int a, int b) {
if (dep[a] < dep[b]) swap(a, b);
int h = dep[a] - dep[b];
for (int i = 0; (1 << i) <= h; ++i) {
if (h >> i & 1) a = up[a][i];
}
if (a == b) return a;
h = __lg(dep[a]);
for (int i = h; i >= 0; --i) {
if (up[a][i] != up[b][i]) {
a = up[a][i];
b = up[b][i];
}
}
return up[a][0];
}
int dist(int a, int b) {
int lca = LCA(a, b);
return sumWeight[a] + sumWeight[b] - 2 * sumWeight[lca];
}
void calc(int u, int p) {
sz[u] = 1;
for (pair<int, int> &x : g[u]) {
int v, w; tie(v, w) = x;
if (blocked[v] || v == p) continue;
calc(v, u);
sz[u] += sz[v];
}
}
int FindCentroid(int u, int p, int SZ) {
for (pair<int, int> &x : g[u]) {
int 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(int curNode, int preCentroid) {
calc(curNode, 0);
int c = FindCentroid(curNode, 0, sz[curNode] / 2);
par[c] = preCentroid;
blocked[c] = true;
for (pair<int, int> &x : g[c]) {
int v, w; tie(v, w) = x;
if (blocked[v]) continue;
decompose(v, c);
}
}
void update(int curNode) {
int fixed = curNode;
while (curNode != 0) {
minimize(bestVal[curNode], dist(fixed, curNode));
curNode = up[curNode][0];
}
}
void reset(int curNode) {
int fixed = curNode;
while (curNode != 0) {
bestVal[curNode] = 1e15;
curNode = up[curNode][0];
}
}
int query(int curNode) {
int fixed = curNode;
int res = INF;
while (curNode != 0) {
minimize(res, bestVal[curNode] + dist(curNode, fixed));
curNode = up[curNode][0];
}
return res;
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
FOR(i, 1, n - 1){
int u = A[i - 1];
int v = B[i - 1];
int w = D[i - 1];
u++;
v++;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
preCalc(1, 0);
prepareLCA();
decompose(1, 0);
FOR(i, 1, n) bestVal[i] = 1e15;
}
long long Query(int S, int X[], int T, int Y[]) {
vector<int> tmpNode;
FOR(i, 1, S) {
int curNode = X[i - 1];
curNode++;
update(curNode);
tmpNode.push_back(curNode);
}
int res = INF;
FOR(i, 1, T) {
int curNode = Y[i - 1];
curNode++;
minimize(res, query(curNode));
}
for (int &curNode : tmpNode) reset(curNode);
return res;
}
//void solve() {
// cin >> n >> q;
// FOR(i, 1, n - 1) {
// int u, v, w; cin >> u >> v >> w;
// u++; v++;
// g[u].push_back({v, w});
// g[v].push_back({u, w});
// }
// preCalc(1, 0);
// prepareLCA();
// decompose(1, 0);
// FOR(i, 1, n) bestVal[i] = 1e15;
// FOR(node1, 1, n) FOR(node2, 1, n) {
// cerr << "test: " << node1 - 1 << ' ' << node2 - 1 << ' ' << dist(node1, node2) << '\n';
// }
// FOR(Nium, 1, q) {
// int S, T; cin >> S >> T;
// vector<int> tmpNode;
// FOR(i, 1, S) {
// int curNode; cin >> curNode;
// curNode++;
// update(curNode);
// tmpNode.push_back(curNode);
// }
// int res = INF;
// FOR(i, 1, T) {
// int curNode; cin >> curNode;
// curNode++;
// minimize(res, query(curNode));
// }
// for (int &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;
//}
