/*input
*/
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#include "factories.h"
using namespace std;
namespace my_template {
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;
#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"
const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;
template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }
template<typename T>
void print(vector<T> vec, string name = "") {
cout << name;
for (auto u : vec)
cout << u << ' ';
cout << '\n';
}
}
using namespace my_template;
const int MOD = 1000000007;
const ll INF = 1e14;
const int MX = 500101;
const int L = 19;
int n;
vector<vector<pair<int, ll>>> edges;
vi dep;
vl toRoot;
vii p;
vll w;
vi in;
vi out;
int piv;
void dfs(int x, int par) {
in[x] = piv++;
for (auto u : edges[x]) {
if (u.x == par) continue;
int b = u.x;
dep[b] = dep[x] + 1;
toRoot[b] = toRoot[x] + u.y;
p[b][0] = x;
w[b][0] = u.y;
for (int i = 1; i < L; ++i)
{
p[b][i] = p[p[b][i - 1]][i - 1];
w[b][i] = w[b][i - 1] + w[p[b][i - 1]][i - 1];
}
dfs(u.x, x);
}
out[x] = piv;
}
// a is ancestor of b
int anc(int a, int b) {
return in[a] < in[b] and out[b] <= out[a];
}
int lca(int a, int b) {
if (dep[a] > dep[b]) swap(a, b);
// a
// b
for (int i = L - 1; i >= 0; --i)
{
if (dep[b] - (1 << i) >= dep[a])
b = p[b][i];
}
assert(dep[a] == dep[b]);
if (a == b) return a;
for (int i = L - 1; i >= 0; i--)
{
if (p[a][i] != p[b][i]) {
a = p[a][i];
b = p[b][i];
}
}
return p[a][0];
}
ll dis(int a, int b) {
int l = lca(a, b);
return toRoot[a] + toRoot[b] - 2 * toRoot[l];
}
void make_lca() {
dep = vi(n);
p = vii(n, vi(L, 0));
w = vll(n, vl(L, 0));
toRoot = vl(n);
in = vi(n);
out = vi(n);
dep[0] = 0;
p[0][0] = 0;
w[0][0] = 0;
toRoot[0] = 0;
piv = 0;
dfs(0, -1);
}
vi kas;
vll low;
void Init(int N, int A[], int B[], int D[]) {
n = N;
edges.resize(N);
kas = vi(N, -1);
for (int i = 0; i < N - 1; ++i)
{
int a = A[i];
int b = B[i];
int d = D[i];
edges[a].emplace_back(b, d);
edges[b].emplace_back(a, d);
}
make_lca();
low = vll(n, vl{INF, INF});
}
ll Query(int S, int X[], int T, int Y[]) {
vi visi;
for (int i = 0; i < S; ++i) {
visi.emplace_back(X[i]);
kas[X[i]] = 1;
}
for (int i = 0; i < T; ++i) {
visi.emplace_back(Y[i]);
kas[Y[i]] = 2;
}
sort(visi.begin(), visi.end(), [&](const int & a, const int & b) {
return in[a] < in[b];
});
for (int i = 1; i < S + T; ++i)
{
int l = lca(visi[i - 1], visi[i]);
visi.emplace_back(l);
if (kas[l] == -1)
kas[l] = 0;
}
sort(visi.begin(), visi.end(), [&](const int & a, const int & b) {
return in[a] < in[b];
});
visi.erase(unique(visi.begin(), visi.end()), visi.end());
// print(visi);
ll ats = INF;
vector<int> ver;
ver.emplace_back(visi[0]);
if (kas[visi[0]]) low[visi[0]][kas[visi[0]] - 1] = 0;
for (int i = 1; i < (int)visi.size(); ++i)
{
while (!anc(ver.back(), visi[i])) {
int a = ver.back(); ver.pop_back();
int b = ver.back();
ll d = dis(a, b);
if (kas[a] + kas[b] == 3)
ats = min(ats, d);
// b
// / c
// a
low[b][0] = min(low[b][0], low[a][0] + d);
low[b][1] = min(low[b][1], low[a][1] + d);
}
ver.emplace_back(visi[i]);
if (kas[visi[i]]) low[visi[i]][kas[visi[i]] - 1] = 0;
}
while (ver.size() >= 2) {
int a = ver.back(); ver.pop_back();
int b = ver.back();
ll d = dis(a, b);
// printf("a = %d, b = %d, d = %lld\n", a, b, d);
if (kas[a] + kas[b] == 3)
ats = min(ats, d);
// b
// / c
// a
low[b][0] = min(low[b][0], low[a][0] + d);
low[b][1] = min(low[b][1], low[a][1] + d);
}
for (auto u : visi) {
// printf("u = %d, low = %lld %lld\n", u, low[u][0], low[u][1]);
ats = min(ats, low[u][0] + low[u][1]);
kas[u] = -1;
low[u][0] = low[u][1] = INF;
}
return ats;
}
