#include "factories.h"
#include<bits/stdc++.h>
#define ll long long
#define lll __int128_t
#define f first
#define s second
using namespace std;
const int mod = 1e9 + 7;
const int N = 5e5 + 5, M = 1e6 + 5;
const int base = 311;
const ll INF = LLONG_MAX;
const int inf = INT_MAX;
int n, q, depth[N], tin[N], tout[N], dfs_timer, par[N][20];
ll dis[N];
vector<pair<int, int>> g[N];
void dfs(int u, int e){
tin[u] = ++dfs_timer;
for(auto [v, w] : g[u]) if(v != e){
depth[v] = depth[u] + 1; par[v][0] = u; dis[v] = dis[u] + w;
for(int i = 1; i <= 18; ++i){
par[v][i] = par[par[v][i-1]][i-1];
}
dfs(v, u);
}
tout[u] = dfs_timer;
}
bool dfsTimer(int u, int v){
return tin[u] < tin[v];
}
bool inside(int u, int v){
return tin[u] <= tin[v] and tout[v] <= tout[u];
}
int getLCA(int u, int v){
if(inside(u, v)) return u;
if(inside(v, u)) return v;
for(int i = 18; i >= 0; --i){
if(depth[u] >= (1<<i) and !inside(par[u][i], v)){
u = par[u][i];
}
}
return par[u][0];
}
int k, ns, nt, a[N];
vector<pair<int, ll>> minigraph[N];
stack<int> st;
short ds[N], d[N];
ll dp[3][N];
void solve(int u, int e){
dp[1][u] = dp[2][u] = INF;
if(ds[u]) dp[ds[u]][u] = 0;
for(auto [v, w] : minigraph[u]){
solve(v, u);
if(dp[1][v] != INF) dp[1][u] = min(dp[1][u], dp[1][v] + w);
if(dp[2][v] != INF) dp[2][u] = min(dp[2][u], dp[2][v] + w);
}
}
long long Query(int S, int X[], int T, int Y[]){
ns = S; nt = T;
for(int i = 1; i <= ns; ++i){
a[i] = X[i - 1];
ds[a[i]] = 1;
}
for(int i = ns + 1; i <= ns + nt; i++){
a[i] = Y[i - ns - 1];
ds[a[i]] = 2;
}
k = ns + nt;
sort(a + 1, a + 1 + k, dfsTimer);
for(int i = 1; i < k; ++i){
a[i+k] = getLCA(a[i], a[i+1]);
}
k = 2 * k - 1;
sort(a + 1, a + 1 + k, dfsTimer);
k = unique(a + 1, a + 1 + k) - a - 1;
while(!st.empty()) st.pop();
st.push(a[1]);
for(int i = 2; i <= k; ++i){
while(!inside(st.top(), a[i])){
st.pop();
}
minigraph[st.top()].push_back({a[i], dis[a[i]] - dis[st.top()]});
st.push(a[i]);
}
solve(a[1], -1); ll ans = INF;
for(int i = 1; i <= k; i++){
int u = a[i];
if(dp[1][u] != INF && dp[2][u] != INF) ans = min(ans, dp[1][u] + dp[2][u]);
}
for(int i = 1; i <= k; i++){
minigraph[a[i]].clear();
ds[a[i]] = 0;
}
return ans;
}
void Init(int N, int A[], int B[], int D[]){
n = N;
for(int i=1; i<n; ++i){
int u = A[i - 1], v = B[i - 1], w = D[i - 1];
g[u].push_back({v, w});
g[v].push_back({u, w});
}
for(int i = 1; i <= n; i++){
ds[i] = 0;
}
dfs(0, 0);
}
