#ifndef FACTORIES_H
#define FACTORIES_H
void Init(int N, int A[], int B[], int D[]);
long long Query(int S, int X[], int T, int Y[]);
#endif
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
static const int MAXN = 500000;
static const int LG = 20;
int tin[MAXN+5], tout[MAXN+5], depth[MAXN+5];
long long dis[MAXN+5];
int f[MAXN+5][LG];
vector<pair<int,int>> g[MAXN+5];
int tdfs;
void dfs(int u, int p) {
tin[u] = ++tdfs;
f[u][0] = p;
for (auto &e : g[u]) {
int v = e.first, w = e.second;
if (v == p) continue;
depth[v] = depth[u] + 1;
dis[v] = dis[u] + w;
dfs(v, u);
}
tout[u] = tdfs;
}
int lca(int x, int y) {
if (depth[x] < depth[y]) swap(x, y);
int diff = depth[x] - depth[y];
for (int j = 0; j < LG; j++) if (diff >> j & 1) x = f[x][j];
if (x == y) return x;
for (int j = LG-1; j >= 0; j--) if (f[x][j] != f[y][j]) {
x = f[x][j];
y = f[y][j];
}
return f[x][0];
}
void Init(int N, int A[], int B[], int D[]) {
tdfs = 0;
for (int i = 0; i < N; i++) {
g[i].clear(); depth[i] = 0; dis[i] = 0;
for (int j = 0; j < LG; j++) f[i][j] = 0;
}
for (int i = 0; i < N-1; i++) {
g[A[i]].push_back({B[i], D[i]});
g[B[i]].push_back({A[i], D[i]});
}
dfs(0, 0);
for (int j = 1; j < LG; j++)
for (int i = 0; i < N; i++)
f[i][j] = f[ f[i][j-1] ][j-1];
}
long long Query(int S, int X[], int T, int Y[]) {
vector<int> vs;
vs.reserve(S+T);
for (int i = 0; i < S; i++) vs.push_back(X[i]);
for (int i = 0; i < T; i++) vs.push_back(Y[i]);
sort(vs.begin(), vs.end(), [&](int a, int b){ return tin[a] < tin[b]; });
int m0 = vs.size();
for (int i = 1; i < m0; i++)
vs.push_back(lca(vs[i-1], vs[i]));
sort(vs.begin(), vs.end(), [&](int a, int b){ return tin[a] < tin[b]; });
vs.erase(unique(vs.begin(), vs.end()), vs.end());
int M = vs.size();
unordered_map<int,int> idx;
for (int i = 0; i < M; i++) idx[vs[i]] = i;
vector<vector<int>> tree(M);
vector<int> st;
st.push_back(vs[0]);
for (int i = 1; i < M; i++) {
while (!(tin[st.back()] <= tin[vs[i]] && tout[vs[i]] <= tout[st.back()]))
st.pop_back();
int u = st.back(), v = vs[i];
tree[ idx[u] ].push_back(idx[v]);
st.push_back(v);
}
const long long INF = LLONG_MAX/4;
vector<long long> fa(M, INF), fb(M, INF);
for (int i = 0; i < S; i++) fa[ idx[X[i]] ] = 0;
for (int i = 0; i < T; i++) fb[ idx[Y[i]] ] = 0;
long long ans = INF;
function<void(int)> dfsdp = [&](int u) {
for (int v : tree[u]) {
dfsdp(v);
long long d = dis[vs[u]] + dis[vs[v]] - 2*dis[lca(vs[u], vs[v])];
fa[u] = min(fa[u], fa[v] + d);
fb[u] = min(fb[u], fb[v] + d);
}
ans = min(ans, fa[u] + fb[u]);
};
dfsdp(0);
return ans;
}
