#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<long long, long long>>> centroids;
vector<long long> best;
void updateSub(long long x, long long p, vector<vector<pair<long long, long long>>> &AR, vector<long long> &subtree, vector<long long> &done)
{
subtree[x] = 1;
for (long long i = 0; i < AR[x].size(); i++)
{
if (done[AR[x][i].first])
continue;
if (AR[x][i].first == p)
continue;
updateSub(AR[x][i].first, x, AR, subtree, done);
subtree[x] += subtree[AR[x][i].first];
}
}
void addCentre(long long x, long long p, long long centre, vector<vector<pair<long long, long long>>> &AR, vector<long long> &done, long long dist)
{
centroids[x].push_back({centre, dist});
for (long long i = 0; i < AR[x].size(); i++)
{
if (AR[x][i].first == p)
continue;
if (done[AR[x][i].first])
continue;
addCentre(AR[x][i].first, x, centre, AR, done, dist + AR[x][i].second);
}
}
void decompose(long long x, vector<vector<pair<long long, long long>>> &AR, vector<long long> &done, vector<long long> &subtree)
{
updateSub(x, x, AR, subtree, done);
long long centre = x, last = x;
while (true)
{
long long next = -1;
for (long long i = 0; i < AR[centre].size(); i++)
{
if (done[AR[centre][i].first])
continue;
if (AR[centre][i].first == last)
continue;
if (subtree[AR[centre][i].first] > subtree[x] / 2)
next = AR[centre][i].first;
}
if (next == -1)
break;
last = centre;
centre = next;
}
done[centre] = 1;
addCentre(centre, centre, centre, AR, done, 0);
for (int i = 0; i < AR[centre].size(); i++)
{
if (done[AR[centre][i].first])
continue;
decompose(AR[centre][i].first, AR, done, subtree);
}
}
void Init(int N, int A[], int B[], int D[])
{
vector<vector<pair<long long, long long>>> AR(N);
vector<long long> done(N);
for (long long i = 0; i < N - 1; i++)
{
AR[A[i]].push_back({B[i], D[i]});
AR[B[i]].push_back({A[i], D[i]});
}
centroids.assign(N, {});
best.assign(N, 123456789123456789);
vector<long long> subtree(N);
decompose(0, AR, done, subtree);
}
long long Query(int S, int X[], int T, int Y[])
{
for (int i = 0; i < S; i++)
{
for (int j = 0; j < centroids[X[i]].size(); j++)
{
best[centroids[X[i]][j].first] = min(best[centroids[X[i]][j].first], centroids[X[i]][j].second);
}
}
long long ans = 123456789123456789;
for (int i = 0; i < T; i++)
{
for (int j = 0; j < centroids[Y[i]].size(); j++)
{
ans = min(ans, best[centroids[Y[i]][j].first] + centroids[Y[i]][j].second);
}
}
for (int i = 0; i < S; i++)
{
for (int j = 0; j < centroids[X[i]].size(); j++)
{
best[centroids[X[i]][j].first] = 123456789123456789;
}
}
return ans;
}
/*int main()
{
int N, Q;
cin >> N >> Q;
int A[N - 1], B[N - 1], D[N - 1];
for (int i = 0; i < N - 1; i++)
{
cin >> A[i] >> B[i] >> D[i];
}
Init(N, A, B, D);
for (int i = 0; i < Q; i++)
{
int S, T;
cin >> S >> T;
int X[S], Y[T];
for (int j = 0; j < S; j++)
{
cin >> X[j];
}
for (int j = 0; j < T; j++)
{
cin >> Y[j];
}
cout << Query(S, X, T, Y) << endl;
}
}*/
