//#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
const ll N = 500000 + 6, inf = (ll)1e18;
vector<pll> adj[N];
ll n, timer = 0;
ll tin[N], tout[N], d[N], up[N][21];
ll distv[N], mark[N];
vector<pll> aux[N];
priority_queue<pll, vector<pll>, greater<pll>> pq;
void dfs(ll p, ll u) {
tin[u] = ++timer;
for (auto [v,w] : adj[u]) {
if (v == p) continue;
d[v] = d[u] + w;
up[v][0] = u;
for (int j = 1; j <= 20; ++j)
up[v][j] = up[ up[v][j-1] ][j-1];
dfs(u, v);
}
tout[u] = timer;
}
bool is_anc(ll u, ll v) {
return tin[u] <= tin[v] && tout[v] <= tout[u];
}
ll lca(ll u, ll v) {
if (is_anc(u, v)) return u;
if (is_anc(v, u)) return v;
for (int j = 20; j >= 0; --j)
if (up[u][j] && !is_anc(up[u][j], v)) u = up[u][j];
return up[u][0];
}
bool cmp(ll a, ll b) { return tin[a] < tin[b]; }
void dijkstra(vll& src) {
while (!pq.empty()) pq.pop();
for (ll s : src) {
distv[s] = 0;
pq.push({0, s});
}
while (!pq.empty()) {
auto [du, u] = pq.top(); pq.pop();
if (du != distv[u]) continue;
for (auto [v,w] : aux[u]) {
if (du + w < distv[v]) {
distv[v] = du + w;
pq.push({distv[v], v});
}
}
}
}
/* ===================== IOI MANDATED FUNCTIONS ===================== */
void Init(int Nn, int A[], int B[], int Dd[]) {
n = Nn;
for (int i = 1; i <= n; ++i) {
adj[i].clear();
for (int j = 0; j <= 20; ++j)
up[i][j] = 0;
}
for (int i = 0; i < n-1; ++i) {
int u = A[i] + 1;
int v = B[i] + 1;
int w = Dd[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
timer = 0;
d[1] = 0;
dfs(-1, 1);
}
long long Query(int S, int X[], int T, int Y[]) {
vll v, v1, v2;
for (int i = 0; i < S; ++i) {
int x = X[i] + 1;
v.push_back(x);
v1.push_back(x);
mark[x] = 1;
}
for (int i = 0; i < T; ++i) {
int x = Y[i] + 1;
v.push_back(x);
v2.push_back(x);
mark[x] = 2;
}
sort(v.begin(), v.end(), cmp);
int sz = v.size();
for (int i = 0; i < sz - 1; ++i)
v.push_back(lca(v[i], v[i+1]));
sort(v.begin(), v.end(), cmp);
v.erase(unique(v.begin(), v.end()), v.end());
stack<ll> st;
for (ll u : v) {
if (!st.empty() && !is_anc(st.top(), u))
while (!st.empty() && !is_anc(st.top(), u)) st.pop();
if (!st.empty()) {
ll p = st.top();
ll w = d[u] - d[p];
aux[u].push_back({p, w});
aux[p].push_back({u, w});
}
st.push(u);
}
for (ll x : v) distv[x] = inf;
dijkstra(v1);
ll ans = inf;
for (ll u : v) if (mark[u] == 2) ans = min(ans, distv[u]);
for (ll u : v) {
aux[u].clear();
mark[u] = 0;
distv[u] = inf;
}
return ans;
}
