#include <bits/stdc++.h>
//#pragma GCC optimize ("O2")
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("Ofast")
//#pragma GCC optimize ("strict-overflow")
//#pragma GCC target("avx,avx2,fma")
//#pragma comment(linker, "/STACK:268435456");
#define pb push_back
#define mp make_pair
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
const ll inf = 1e16;
bool blocked[500001];
int n, children[500001], par[500001], cnt[500001], uniRoot;
ll ans = 1e16, dis[500001][19];
vector<pair<int, int>> adj[500001];
gp_hash_table<int, ll> minDis;
void DFS(int u, int prv){
children[u] = 1;
for(auto& i: adj[u]){
if(blocked[i.first] || i.first == prv) continue;
DFS(i.first, u);
children[u] += children[i.first];
}
}
int secDFS(int u, int prv){
bool flag = 1;
for(auto& i: adj[u]) if(! blocked[i.first] && children[i.first]*2 > children[u]) flag = 0;
if(flag) return u;
int anc = -1;
for(auto& i: adj[u]){
if(i.first == prv || blocked[i.first]) continue;
children[u] -= children[i.first];
children[i.first] += children[u];
if(anc == -1) anc = secDFS(i.first, u);
children[i.first] -= children[u];
children[u] += children[i.first];
}
return anc;
}
void distDFS(int u, int prv, ll curDis, int root){
dis[u][cnt[u]++] = curDis;
for(auto& i: adj[u]){
if(blocked[i.first] || i.first == prv) continue;
distDFS(i.first, u, curDis+i.second, root);
}
}
int decompose(int u){
DFS(u, -1);
int root = secDFS(u, -1);
distDFS(root, -1, 0, root);
blocked[root] = 1;
for(auto& i: adj[root]) {
if(blocked[i.first]) continue;
int nextRoot = decompose(i.first);
par[nextRoot] = root;
}
return root;
}
void Init(int N, int A[], int B[], int C[]) {
n = N;
for(int i = 0; i < N-1; i++){
adj[A[i]].pb(mp(B[i], C[i]));
adj[B[i]].pb(mp(A[i], C[i]));
}
uniRoot = decompose(0);
par[uniRoot] = -1;
}
ll Query(int S, int X[], int T, int Y[]){
//The answer is the lowest LCA for a pair {X_i, Y_j} in the Centroid Tree
//O(STlogN) Naive
//How do we process queries in O((S+T)) or O((S+T)logN)?
//Idea: for all S, update the shortest distance for all nodes between the root of the centroid tree and X_i, and for Y_i, move up the centroid tree and update the answer for each node.
//The height of the centroid tree is O(logN), so we get O((S+T)logN)
//We can use Euler Tour Trick to get distances in O(1)
//Alternatively just store the distances
ans = inf;
minDis.clear();
for(int i = 0; i < S; i++){
int cur = X[i], curcnt = cnt[X[i]]-1;
while(cur != -1){
if(minDis.find(cur) == minDis.end()) minDis[cur] = inf;
minDis[cur] = min(minDis[cur], dis[X[i]][curcnt--]);
cur = par[cur];
}
}
for(int i = 0; i < T; i++){
int cur = Y[i], curcnt = cnt[Y[i]]-1;
while(cur != -1){
if(minDis.find(cur) != minDis.end()) ans = min(ans, minDis[cur]+dis[Y[i]][curcnt]);
curcnt--;
cur = par[cur];
}
}
assert(ans != 0);
return ans;
}
/*
int main() {
cin.sync_with_stdio(NULL);
cin.tie(NULL);
int A[6] = {0, 1, 2, 2, 4, 1}, B[6] = {1, 2, 3, 4, 5, 6}, C[6] = {4, 4, 5, 6, 5, 3};
Init(7, A, B, C);
int X1[2] = {0, 6}, Y1[2] = {3, 4};
cout << Query(2, X1, 2, Y1) << "\n";
int X2[3] = {0, 1, 3}, Y2[2] = {4, 6};
cout << Query(3, X2, 2, Y2) << "\n";
int X3[1] = {2}, Y3[1] = {5};
cout << Query(1, X3, 1, Y3) << "\n";
}
*/
