#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>
using namespace std;
typedef long long ll;
#include "factories.h"
const int N = 5e5 + 7;
const int K = 20;
vector <pair <int, int>> g[N];
int go[K][N];
ll h[N];
int tin[N], tout[N];
int id[N];
int timer = 0;
int n;
void dfs(int u, int p) {
tin[u] = timer++;
go[0][u] = p;
for (int i = 1; i < K; ++i) {
go[i][u] = go[i - 1][go[i - 1][u]];
}
for (auto pr : g[u]) {
int v = pr.first, w = pr.second;
if (v != p) {
h[v] = h[u] + w;
dfs(v, u);
}
}
tout[u] = timer++;
}
bool anc(int a, int b) {
return tin[a] <= tin[b] && tout[b] <= tout[a];
}
int lca(int a, int b) {
if (anc(a, b)) return a;
for (int i = K - 1; i >= 0; --i) {
if (!anc(go[i][a], b)) {
a = go[i][a];
}
}
return go[0][a];
}
ll dist(int a, int b) {
return h[a] + h[b] - 2 * h[lca(a, b)];
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for (int i = 0; i + 1 < n; ++i) {
g[A[i]].push_back({B[i], D[i]});
g[B[i]].push_back({A[i], D[i]});
}
dfs(0, 0);
}
long long Query(int s, int X[], int t, int Y[]) {
vector <int> vr;
for (int i = 0; i < s; ++i) vr.push_back(X[i]);
for (int i = 0; i < t; ++i) vr.push_back(Y[i]);
sort(vr.begin(), vr.end(), [&] (int a, int b) {
return tin[a] < tin[b];
});
{
vector <int> nvr;
for (int i = 0; i < (int)vr.size(); ++i) {
int j = (i + 1) % (int)vr.size();
nvr.push_back(lca(vr[i], vr[j]));
}
for (int x : vr) nvr.push_back(x);
vr = nvr;
sort(vr.begin(), vr.end());
vr.resize(unique(vr.begin(), vr.end()) - vr.begin());
sort(vr.begin(), vr.end(), [&] (int a, int b) {
return tin[a] < tin[b];
});
}
int k = vr.size();
for (int i = 0; i < k; ++i) id[vr[i]] = i;
vector <vector <pair <int, ll>>> ng(k);
vector <int> st;
for (int i = 0; i < k; ++i) {
while (!st.empty() && !anc(st.back(), vr[i])) {
st.pop_back();
}
if (!st.empty()) {
ng[id[st.back()]].push_back({id[vr[i]], dist(st.back(), vr[i])});
ng[id[vr[i]]].push_back({id[st.back()], dist(st.back(), vr[i])});
}
st.push_back(vr[i]);
}
vector <int> tp(k, -1);
for (int i = 0; i < s; ++i) {
tp[id[X[i]]] = 0;
}
for (int i = 0; i < t; ++i) {
tp[id[Y[i]]] = 1;
}
const ll Inf = 1e18;
vector <ll> dp(k, Inf);
vector <ll> sdp(k, Inf);
function <void(int, int)> jhfs = [&] (int u, int p) {
if (tp[u] == 0) dp[u] = 0;
for (auto pr : ng[u]) {
int v = pr.first; ll w = pr.second;
if (v != p) {
jhfs(v, u);
ll x = dp[v] + w;
if (x < dp[u]) {
swap(x, dp[u]);
}
if (x < sdp[u]) {
swap(x, sdp[u]);
}
}
}
};
jhfs(0, 0);
vector <ll> dpU(k, Inf);
function <void(int, int, ll)> zhfs = [&] (int u, int p, ll best) {
if (tp[u] == 0) best = 0;
dpU[u] = best;
for (auto pr : ng[u]) {
int v = pr.first; ll w = pr.second;
if (v != p) {
ll go = best + w;
if (dp[v] + w != dp[u]) {
go = min(go, dp[u] + w);
} else {
go = min(go, sdp[u] + w);
}
zhfs(v, u, go);
}
}
};
zhfs(0, 0, Inf);
ll ans = Inf;
for (int i = 0; i < k; ++i) {
if (tp[i] == 1) {
ans = min(ans, dp[i]);
ans = min(ans, dpU[i]);
}
}
return ans;
}
