#include "factories.h"
#include "bits/stdc++.h"
using namespace std;
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
#define ll long long
#define all(a) (a).begin(), (a).end()
const int MAX_N = 5e5 + 5;
const int LOG = 30;
const ll INF = 1e18;
vector<pair<int, int>> adj[MAX_N];
int par[MAX_N][LOG];
ll dis[MAX_N];
int st[MAX_N];
int fi[MAX_N];
int h[MAX_N];
int timer = 0;
int n;
void dfs0(int u, int p)
{
st[u] = timer++;
par[u][0] = p;
for (int i = 1; i < LOG; i++) par[u][i] = par[par[u][i - 1]][i - 1];
for (auto v : adj[u]) if (v.first != p) h[v.first] = h[u] + 1, dis[v.first] = dis[u] + v.second, dfs0(v.first, u);
fi[u] = timer;
}
int getpar(int u, int k)
{
for (int i = 0; i < LOG; i++) if (k & (1 << i)) u = par[u][i];
return u;
}
int lca(int u, int v)
{
if (h[u] < h[v]) swap(u, v);
u = getpar(u, h[u] - h[v]);
if (u == v) return u;
for (int i = LOG - 1; i >= 0; i--) if (par[u][i] != par[v][i]) u = par[u][i], v = par[v][i];
return par[u][0];
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for (int i = 0; i < N - 1; i++) A[i]++, B[i]++, adj[A[i]].push_back({B[i], D[i]}), adj[B[i]].push_back({A[i], D[i]});
dfs0(1, 0);
}
vector<int> adj2[MAX_N];
int mark[MAX_N];
ll dp[MAX_N][2];
ll ans = INF;
void dfs(int u)
{
dp[u][0] = dp[u][1] = INF;
if (mark[u]) dp[u][mark[u] - 1] = dis[u];
for (auto v : adj2[u]) dfs(v), dp[u][0] = min(dp[u][0], dp[v][0]), dp[u][1] = min(dp[u][1], dp[v][1]);
ans = min(ans, dp[u][0] + dp[u][1] - 2 * dis[u]);
}
long long Query(int S, int X[], int T, int Y[]) {
set<int> al1;
vector<pair<int, int>> al2;
fill(mark, mark + n + 1, 0);
for (int i = 1; i <= n; i++) adj2[i].clear();
for (int i = 0; i < S; i++) X[i]++, al1.insert(X[i]), al2.push_back({st[X[i]], X[i]}), mark[X[i]] = 1;
for (int i = 0; i < T; i++)
{
Y[i]++;
if (al1.find(Y[i]) != al1.end()) return 0;
al2.push_back({st[Y[i]], Y[i]});
mark[Y[i]] = 2;
}
sort(all(al2));
int sz = al2.size();
for (int i = 0; i < sz - 1; i++)
{
int lc = lca(al2[i].second, al2[i + 1].second);
al2.push_back({st[lc], lc});
}
sort(all(al2));
al2.resize(unique(all(al2)) - al2.begin());
vector<int> al3({al2[0].second});
for (int i = 1; i < al2.size(); i++)
{
while (fi[al3.back()] <= al2[i].first) al3.pop_back();
adj2[al3.back()].push_back(al2[i].second);
al3.push_back(al2[i].second);
}
ans = INF;
dfs(al2[0].second);
return ans;
}
