#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
// #define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define maxn 500050
int n, szfc[maxn], block[maxn], h[maxn], pc[maxn], tin[maxn], tout[maxn];
pair<int,int> mnr[maxn][25], mnl[maxn][25];
long long d[maxn], mn[maxn];
vector<int> vfc;
vector<pair<int,int>> g[maxn], el;
void dfsfc(int u, int ant) {
szfc[u] = 1;
vfc.pb(u);
for(auto V : g[u]) {
int v = V.fr;
if(v == ant || block[v]) continue;
dfsfc(v,u);
szfc[u]+= szfc[v];
}
}
void dfslca(int u, int ant) {
tin[u] = el.size();
el.pb(mp(h[u],u));
for(auto V : g[u]) {
int v = V.fr;
int w = V.sc;
if(v == ant) continue;
h[v] = h[u]+1;
d[v] = d[u]+w;
dfslca(v,u);
el.pb(mp(h[u],u));
}
tout[u] = el.size()-1;
}
int lca(int u, int v) {
if(tin[u] >= tin[v] && tout[u] <= tout[v]) {
return v;
}
else if(tin[v] >= tin[u] && tout[v] <= tout[u]) {
return u;
}
if(tin[u] > tin[v]) {
swap(u,v);
}
int l = tout[u];
int r = tin[v];
int p = 32-__builtin_clz(r-l+1);
auto x = min(mnr[l][p], mnl[r][p]);
return x.sc;
}
int fcent(int beg) {
vfc.clear();
dfsfc(beg,beg);
int cent;
for(auto u : vfc) {
bool ok = true;
if(szfc[beg]-szfc[u] > szfc[beg]/2) ok = false;
for(auto V : g[u]) {
int v = V.fr;
if(block[v]) continue;
if(szfc[v] > szfc[u]) continue;
if(szfc[v] > szfc[beg]/2) ok = false;
}
if(ok) cent = u;
}
block[cent] = 1;
for(auto V : g[cent]) {
int v = V.fr;
if(block[v]) continue;
pc[fcent(v)] = cent;
}
return cent;
}
long long Query(int32_t S, int32_t X[], int32_t T, int32_t Y[]) {
long long ans = inf;
for(int i = 0; i < S; i++) {
int v = X[i];
while(v != -1) {
mn[v] = min(mn[v],d[X[i]]+d[v]-2*d[lca(X[i],v)]);
v = pc[v];
}
}
for(int i = 0; i < T; i++) {
int v = Y[i];
while(v != -1) {
ans = min(ans, mn[v]+d[Y[i]]+d[v]-2*d[lca(Y[i],v)]);
v = pc[v];
}
}
for(int i = 0; i < S; i++) {
int v = X[i];
while(v != -1) {
mn[v] = inf;
v = pc[v];
}
}
assert(ans != 3);
return ans;
}
void Init(int32_t N, int32_t A[], int32_t B[], int32_t D[]) {
n = N;
for(int i = 0; i < n-1; i++) {
g[A[i]].pb(mp(B[i],D[i]));
g[B[i]].pb(mp(A[i],D[i]));
}
for(int i = 0; i < n; i++) {
pc[i] = -1;
mn[i] = inf;
}
fcent(0);
dfslca(0,0);
for(int i = 0; i < el.size(); i++) {
mnr[i][0] = el[i];
}
for(int j = 1; j <= 20; j++) {
for(int i = 0; i < el.size(); i++) {
mnr[i][j] = min(mnr[i][j-1],mnr[min((int) el.size()-1, i+(1<<(j-1)))][j-1]);
}
}
for(int i = 0; i < el.size(); i++) {
mnl[i][0] = el[i];
}
for(int j = 1; j <= 20; j++) {
for(int i = 0; i < el.size(); i++) {
mnl[i][j] = min(mnl[i][j-1],mnl[max(0, i-(1<<(j-1)))][j-1]);
}
}
}
// int32_t main() {
// ios::sync_with_stdio(false); cin.tie(0);
// freopen("in.in", "r", stdin);
// //freopen("out.out", "w", stdout);
// int32_t N, Q; cin >> N >> Q;
// int32_t 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);
// while(Q--) {
// int32_t S, T; cin >> S >> T;
// int32_t X[S], Y[T];
// for(int i = 0; i < S; i++) cin >> X[i];
// for(int i = 0; i < T; i++) cin >> Y[i];
// cout << Query(S,X,T,Y) << endl;
// }
// }
