#include <bits/stdc++.h>
#define ll long long
using namespace std;
int N;
bool V[500001];
int SIZE[500001];
queue <pair <int, int>> Q;
vector <pair <int, int>> VG[500001];
vector <pair <ll, int>> UP[500001];
ll DP[500001];
inline void SDFS(int node, int parent = -1)
{
SIZE[node] = 1;
Q.push({node, parent});
for(pair <int, int> p : VG[node])
{
if(V[p.second] || (p.second == parent)) continue;
SDFS(p.second, node);
SIZE[node] += SIZE[p.second];
}
return;
}
inline void DFS(int node, int root, ll depth, int parent = -1)
{
UP[node].push_back({depth, root});
for(pair <int, int> p : VG[node]) if(!V[p.second] && (p.second != parent)) DFS(p.second, root, depth + p.first, node);
return;
}
inline void CD(int root = 1)
{
int centroid, best = INT_MAX, temp;
SDFS(root);
while(Q.size())
{
temp = SIZE[root] - SIZE[Q.front().first];
for(pair <int, int> p : VG[Q.front().first]) if(!V[p.second] && (p.second != Q.front().second)) temp = max(SIZE[p.second], temp);
if(temp < best) {centroid = Q.front().first; best = temp;}
Q.pop();
}
DFS(centroid, centroid, 0);
V[centroid] = 1;
for(pair <int, int> p : VG[centroid]) if(!V[p.second]) CD(p.second);
return;
}
void Init(int n, int u[], int v[], int w[])
{
N = n;
for(int i = 0; i < (N - 1); i++)
{
VG[u[i] + 1].push_back({w[i], v[i] + 1});
VG[v[i] + 1].push_back({w[i], u[i] + 1});
}
CD();
for(int i = 1; i <= N; i++) DP[i] = 1e18;
return;
}
ll Query(int n, int X[], int m, int Y[])
{
ll ret = 1e18;
for(int i = 0; i < n; i++) for(pair <ll, int> p : UP[X[i] + 1]) DP[p.second] = min(p.first, DP[p.second]);
for(int i = 0; i < m; i++) for(pair <ll, int> p : UP[Y[i] + 1]) ret = min(p.first + DP[p.second], ret);
for(int i = 0; i < n; i++) for(pair <ll, int> p : UP[X[i] + 1]) DP[p.second] = 1e18;
return ret;
}
//int main()
//{
// int n, m;
// cin >> n;
// int u[n], v[n], w[n];
// for(int i = 0; i < (n - 1); i++) cin >> u[i] >> v[i] >> w[i];
// Init(n, u, v, w);
// while(true)
// {
// cin >> n >> m;
// int x[n], y[m];
// for(int i = 0; i < n; i++) cin >> x[i];
// for(int i = 0; i < m; i++) cin >> y[i];
// cout << "ans: " << Query(n, x, m, y) << '\n';
// }
//
// return 0;
//}
