#include <iostream>
#include <algorithm>
#include <vector>
#include <random>
#include <chrono>
#include <set>
#include <map>
#include <stack>
#include <functional>
#include <iomanip>
#include <queue>
#include <cassert>
#include <complex>
#include <cstring>
#include <memory>
#include <bitset>
#include <sstream>
#include <cmath>
#include <numeric>
#include <numbers>
#include <fstream>
#include "factories.h"
using namespace std;
#ifndef template
#ifndef define
#define ll long long
#define ld long double
#define pl pair<ll, ll>
#define pi pair<int, int>
#define nl cout << '\n';
#define x first
#define y second
#define cbit(x) __builtin_popcountll(x)
#define uid(a, b) uniform_int_distribution<ll>(a, b)(rng)
#define siz(x) (int)x.size()
#endif
#ifndef print
void print(size_t x) {cout << x << ' ';}
void print(int x) {cout << x << ' ';}
void print(long long x) {cout << x << ' ';}
void print(float x) {cout << x << ' ';}
void print(long double x) {cout << x << ' ';}
void print(char x) {cout << x << ' ';}
void print(const char* x) {cout << x << ' ';}
void print(bool x) {cout << x << ' ';}
void print(string &x) {cout << x << ' ';}
template<typename T, typename V>
void print(pair<T, V> &p) {print(p.x); print(p.y);}
template<typename T>
void print(vector<T> v) {for (int i = 0; i < v.size(); i++) print(v[i]);}
template<typename T>
void print(vector<vector<T>> v) {
for (int i = 0; i < v.size(); i++){
for (int j = 0; j < v[i].size(); j++)
print(v[i][j]);
nl;
}
}
template <typename T, typename... V>
void print(T t, V&&... v) {print(t); print(v...);}
#endif
#ifndef read
void read(int &x) {cin >> x;}
void read(long long &x) {cin >> x;}
void read(unsigned &x) {cin >> x;}
void read(unsigned long long &x) {cin >> x;}
void read(float &x) {cin >> x;}
void read(long double &x) {cin >> x;}
void read(char &x) {cin >> x;}
void read(string &x) {cin >> x;}
void read(bool &x) {cin >> x;}
template<typename T>
void read(vector<T> &v) {
for (int i = 0; i < v.size(); i++)
read(v[i]);
}
template <typename T, typename... V>
void read(T &t, V&... v) {read(t); read(v...);}
#endif
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> bool maxi(T& a, const T& b) {
return a < b ? a = b, 1 : 0;
}
template<class T> bool mini(T& a, const T& b) {
return a > b ? a = b, 1 : 0;
}
template<class... Args>
auto vec(size_t n, Args&&... args) {
if constexpr(sizeof...(args) == 1)
return vector(n, args...);
else
return vector(n, vec(args...));
}
#endif
using namespace std;
const ll inf = 1e18;
const ll def = 5e5+1;
const ll mod = 1e9+9;
using namespace std;
vector<pi> edg[def];
ll order[def], h[def], wi[def];
int par[def], f[def][20];
int crr = 0;
void dfs(int u, int pre){
order[u] = crr++;
for (auto [v, w] : edg[u]){
if (v == pre)
continue;
par[v] = u;
wi[v] = wi[u] + w;
h[v] = h[u] + 1;
dfs(v, u);
}
}
int lca(int u, int v){
if (h[v] < h[u]) swap(u, v);
for (int i = 19; i >= 0; i--){
if (f[v][i] != -1 && h[f[v][i]] >= h[u])
v = f[v][i];
}
if (u == v) return u;
for (int i = 19; i >= 0; i--){
if (f[v][i] != -1 && f[u][i] != -1 && f[v][i] != f[u][i])
u = f[u][i], v = f[v][i];
}
return par[u];
}
void Init(int N, int A[], int B[], int D[]){
for (int i = 0; i < N - 1; i++){
edg[A[i]].push_back({B[i], D[i]});
edg[B[i]].push_back({A[i], D[i]});
}
dfs(0, -1);
for (int i = 0; i < N; i++) for (int j = 0; j < 20; j++)
f[i][j] = -1;
for (int i = 0; i < N; i++)
f[i][0] = par[i];
for (int j = 1; j < 20; j++){
for (int i = 0; i < N; i++){
int p = f[i][j - 1];
if (p != -1)
f[i][j] = f[p][j - 1];
}
}
}
vector<pl> edg2[def];
bool inA[def], inB[def];
ll dp[def], res = inf;
void dfs2(int u, int pre){
if (inB[u])
dp[u] = 0;
for (auto [v, w] : edg2[u]){
if (v == pre)
continue;
dfs2(v, u);
mini(dp[u], dp[v] + w);
}
}
void dfs3(int u, int pre, ll crr){
vector<pl> child;
for (auto [v, w] : edg2[u]){
if (v == pre)
continue;
child.push_back({v, w});
}
int m = child.size();
auto pref = vec(m + 1, inf);
auto suff = pref;
for (int i = 1; i <= m; i++){
auto [v, w] = child[i - 1];
pref[i] = min(pref[i - 1], dp[v] + w);
}
for (int i = m - 1; i >= 0; i--){
auto [v, w] = child[i];
suff[i] = min(suff[i + 1], dp[v] + w);
}
for (int i = 0; i < m; i++){
auto [v, w] = child[i];
dfs3(v, u, min(pref[i], suff[i + 1]) + w);
}
if (inA[u])
mini(res, min(crr, dp[u]));
}
long long Query(int S, int X[], int T, int Y[]){
vector<int> nodes;
for (int i = 0; i < S; i++){
nodes.push_back(X[i]);
inA[X[i]] = 1;
}
for (int i = 0; i < T; i++){
nodes.push_back(Y[i]);
inB[Y[i]] = 1;
}
sort(nodes.begin(), nodes.end(), [](int a, int b){
return order[a] < order[b];
});
int m = nodes.size();
for (int i = 1; i < m; i++){
int p = lca(nodes[i - 1], nodes[i]);
nodes.push_back(p);
}
sort(nodes.begin(), nodes.end(), [](int a, int b){
return order[a] < order[b];
});
nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());
for (int i = 1; i < nodes.size(); i++){
dp[nodes[i]] = dp[nodes[i - 1]] = inf;
int u = nodes[i], v = lca(u, nodes[i - 1]), w = wi[u] - wi[v];
edg2[u].push_back({v, w});
edg2[v].push_back({u, w});
}
int root = nodes[0]; res = inf;
dfs2(root, -1);
dfs3(root, -1, inf);
for (int i = 0; i < nodes.size(); i++){
int u = nodes[i];
edg2[u].clear();
inA[u] = inB[u] = 0;
}
return res;
}
// void solve(){
// int n, q;
// read(n, q);
// int A[n - 1], B[n - 1], D[n - 1];
// for (int i = 0; i < n - 1; i++)
// read(A[i], B[i], D[i]);
// Init(n, A, B, D);
// while (q--){
// int S, T;
// read(S, T);
// int X[S], Y[T];
// for (int i = 0; i < S; i++)
// read(X[i]);
// for (int i = 0; i < T; i++)
// read(Y[i]);
// print(Query(S, X, T, Y)); nl;
// }
// }
// int32_t main(){
// ios_base::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
// if (ifstream("input.txt").good()){
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// }
// int t = 1;
// while (t--){
// solve();
// nl;
// }
// return 0;
// }
