#include <bits/stdc++.h>
#define ll long long
using namespace std;
int N;
bool V[500001];
int SIZE[500001];
vector <pair <int, int>> VG[500001];
vector <pair <ll, int>> UP[500001];
ll DP[500001];
inline int SDFS(int node, int parent = -1)
{
SIZE[node] = 1;
for(pair <int, int> p : VG[node]) if(!V[p.second] && (p.second != parent)) SIZE[node] += SDFS(p.second, node);
return SIZE[node];
}
inline int CDFS(int node, int num, int parent = -1)
{
int temp = 0;
for(pair <int, int> p : VG[node]) if((!V[p.second] && (p.second != parent)) && (SIZE[p.second] > SIZE[temp])) temp = p.second;
if(SIZE[temp] <= num) return temp;
return CDFS(temp, num, node);
}
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)
{
SDFS(root);
int centroid = CDFS(root, (SIZE[root] + 1) >> 1);
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;
//}
