#include "factories.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#include <cassert>
#include <bitset>
#include <random>
#include <chrono>
#include <cstring>
#define ll long long
#define ld long double
//#define int ll
#define For(i, n) for(int i = 0; i < (int)n; i++)
#define ffor(i, a, n) for(int i = (int)a; i < (int)n; i++)
#define rfor(i, n) for(int i = (int)n; i >= (int)0; i--)
#define rffor(i, a, n) for(int i = (int)n; i >= (int)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<int, int>
#define pld pair<ld, ld>
#define NEK 2000000000
#define mod 1000000007
#define mod2 1000000009
#define rsz resize
#define prv 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define all(x) (x).begin(), (x).end()
#define sig 0.0000001
using namespace std;
const int M = 21;
vec<vec<pii>> g;
vec<vec<pii>> pred;
vec<bool> je;
vec<int> podst;
vec<int> hod;
void vpodst(int x, int pr = -1) {
podst[x] = 1;
for (auto &i : g[x]) {
if (i.ff == pr || je[i.ff]) continue;
vpodst(i.ff, x);
podst[x] += podst[i.ff];
}
return;
}
int centroid(int x, int vel, int pr = -1) {
for (auto &i : g[x]) {
if (je[i.ff] || i.ff == pr) continue;
if (podst[i.ff] * 2 > vel) {
return centroid(i.ff, vel, x);
}
}
return x;
}
void pocitaj_pred(int x, int c, int pr = -1, int dist = -1) {
pred[x].push_back({ c, dist });
for (auto i : g[x]) {
if (je[i.ff] || i.ff == pr) continue;
pocitaj_pred(i.ff, c, x, dist + i.ss);
}
return;
}
void build_centroid(int x = 0) {
vpodst(x);
int c = centroid(x, podst[x]);
je[c] = 1;
for (auto &i : g[c]) {
if (je[i.ff]) continue;
pocitaj_pred(i.ff, c, c, i.ss);
build_centroid(i.ff);
}
return;
}
void Init(int n, int a[], int b[], int d[]) {
g.resize(n);
hod.resize(n, NEK);
podst.resize(n, 1);
For(i, n-1) {
g[a[i]].push_back({ b[i], d[i] });
g[b[i]].push_back({ a[i], d[i] });
}
pred.resize(n);
je.resize(n, 0);
build_centroid();
}
ll Query(int s, int x[], int t, int y[]) {
For(i, s) {
hod[x[i]] = 0;
for (auto &j : pred[x[i]]) {
hod[j.ff] = min(hod[j.ff], j.ss);
}
}
int mini = NEK;
For(i, t) {
for (auto& j : pred[y[i]]) {
mini = min(mini, hod[j.ff] + j.ss);
}
}
For(i, s) {
hod[x[i]] = NEK;
for (auto& j : pred[x[i]]) {
hod[j.ff] = NEK;
}
}
return mini;
}
/*
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n; cin >> n;
int q; cin >> q;
vec<int> a(n), b(n), d(n);
For(i, n - 1) {
cin >> a[i] >> b[i] >> d[i];
}
Init(n, a, b, d);
For(i, q) {
int s, t; cin >> s >> t;
vec<int> x(s), y(t);
For(j, s) {
cin >> x[j];
}
For(j, t) {
cin >> y[j];
}
cout << Query(s, x, t, y) << '\n';
}
return 0;
}*/
