#include "bits/stdc++.h"
#include "factories.h"
using namespace std;
#define ln "\n"
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define ll long long
const int mod = 1e9 + 7;
const ll inf = 2e18;
const int N = 1e6 + 7;
vector<pair<int, ll>> g[N], sg[N];
int h[N];
ll lev[N];
int in[N], lg[N], out[N];
pair<int, int> rmq[N * 2][25];
int label[N];
ll dp[N][2], f[N];
int timer = 0;
void dfs(int u, int p) {
in[u] = ++timer;
// cerr << "TURN " << u << ' ' << lev[u] << ' ' << h[u] << ln;
rmq[timer][0] = {h[u], u};
for(auto x : g[u]) {
int v = x.fi;
ll w = x.se;
if(v == p) continue;
h[v] = h[u] + 1;
// cerr << u << "TO " << v << " " << w << ln;
lev[v] = lev[u] + w;
dfs(v, u);
rmq[++timer][0] = {h[u], u};
}
out[u] = timer;
}
int lca(int u, int v) {
int l = in[u], r = in[v];
// cerr << u << ' ' << v << ' ' << l << ' ' << r << ln;
if(l > r) swap(l, r);
int k = lg[r - l + 1];
return min(rmq[l][k], rmq[r - (1 << k) + 1][k]).se;
}
ll dist(int u, int v) {
return lev[u] + lev[v] - 2 * lev[lca(u, v)];
}
bool inside(int x, int y) {
return out[x] >= in[y];
}
void Init(int n, int a[], int b[], int d[]) {
timer = 0;
for(int i = 0; i < n - 1; i++) {
int u = a[i] + 1, v = b[i] + 1;
g[u].pb({v, d[i]});
g[v].pb({u, d[i]});
}
dfs(1, 0);
// for(int i = 1; i <= n; i++) cerr << i << ' ' << lev[i] << ln;
for(int i = 2; i <= timer; i++) lg[i] = lg[i / 2] + 1;
for(int j = 1; (1 << j) <= timer; j++) {
for(int i = 1; i + (1 << j) <= timer; i++) {
rmq[i][j] = min(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
}
}
for(int i = 1; i <= n; i++) dp[i][0] = dp[i][1] = inf;
}
ll Query(int s, int x[], int t, int y[]) {
vector<int> vec;
for(int i = 0; i < s; i++) {
x[i]++;
vec.pb(x[i]);
dp[x[i]][0] = lev[x[i]];
}
for(int i = 0; i < t; i++) {
y[i]++;
vec.pb(y[i]);
dp[y[i]][1] = lev[y[i]];
}
sort(all(vec), [&](const int x, const int y) {
return in[x] < in[y];
});
int m = sz(vec);
for(int i = 1; i < m; i++) {
vec.pb(lca(vec[i], vec[i - 1]));
}
sort(all(vec), [&](const int x, const int y) {
return in[x] < in[y];
});
vec.erase(unique(all(vec)), vec.end());
stack<int> st;
for(int x : vec) {
while(sz(st) and !inside(st.top(), x)) st.pop();
if(sz(st)) {
ll w = dist(x, st.top());
sg[st.top()].pb({x, w});
}
st.push(x);
}
reverse(all(vec));
ll ans = inf;
for(int u : vec) {
for(auto y : sg[u]) {
int v = y.fi, w = y.se;
dp[u][1] = min(dp[u][1], dp[v][1]);
dp[u][0] = min(dp[u][0], dp[v][0]);
}
ans = min(ans, dp[u][1] + dp[u][0] - 2 * lev[u]);
}
for(int u: vec) sg[u].clear(), dp[u][0] = dp[u][1] = inf;
return ans;
}
//TESTING
// int A[N], B[N], D[N];
// int X[N], Y[N];
// signed main() {
// cin.tie(0) -> sync_with_stdio(0);
// int n, q; cin >> n >> q;
// for(int i = 0; i < n - 1; i++) {
// int u, v, w; cin >> u >> v >> w;
// A[i] = u, B[i] = v, D[i] = w;
// }
// Init(n, A, B, D);
// for(int i = 1; i <= q; i++) {
// int s, t; cin >> s >> 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) << ln;
// for(int i = 0; i < s; i++) {
// X[i] = 0;
// }
// for(int i = 0; i < t; i++) {
// Y[i] = 0;
// }
// }
// }
