#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(ll i = 0; i < (ll)n; i++)
#define ffor(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define rfor(i, n) for(ll i = (ll)n; i >= (ll)0; i--)
#define rffor(i, a, n) for(ll i = (ll)n; i >= (ll)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<ll, ll>
#define pld pair<ld, ld>
#define NEK 2000000000000000
#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;
vec<vec<pii>> g;
vec<vec<pii>> pred;
vec<bool> je;
vec<ll> podst;
vec<ll> hod;
void vpodst(ll x, ll 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;
}
ll centroid(ll x, ll vel, ll 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(ll x, ll c, ll pr = -1, ll 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(ll x = 0) {
vpodst(x);
ll 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 n2, int a2[], int b2[], int d2[]) {
ll n = n2;
vec<ll> a, b, d;
For(i, n - 1) {
a.push_back(a2[i]);
b.push_back(b2[i]);
d.push_back(d2[i]);
}
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 s2, int x2[], int t2, int y2[]) {
ll s = s2, t = t2;
vec<ll> x, y;
For(i, s) x.push_back(x2[i]);
For(i, t) y.push_back(y2[i]);
For(i, s) {
hod[x[i]] = 0;
for (auto &j : pred[x[i]]) {
hod[j.ff] = min(hod[j.ff], j.ss);
}
}
ll mini = NEK;
For(i, t) {
mini = min(mini, hod[y[i]]);
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;
int a[100], b[100], d[100];
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;
int x[100], y[100];
For(j, s) {
cin >> x[j];
}
For(j, t) {
cin >> y[j];
}
cout << Query(s, x, t, y) << '\n';
}
return 0;
}*/
