#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
const long long INF = 4e18;
vector<int> tin;
vector<vector<pair<int, int> > > adj;
vector<vector<pair<int, long long> > > adj2;
vector<long long> pref;
int timer = 0;
long long ans = 0;
vector<long long> dpX;
vector<long long> dpY;
vector<bool> isX;
vector<bool> isY;
vector<int> level;
vector<vector<long long> > dp(21);
bool sort_tin(const int &a, const int &b){
return tin[a] < tin[b];
}
void dfs(int u, int p){
if(p == -1) dp[0][u] = u;
else dp[0][u] = p;
tin[u] = timer++;
for(pair<int, int> x : adj[u]){
int v = x.first;
if(v != p){
pref[v] = pref[u] + x.second;
level[v] = level[u] + 1;
dfs(v, u);
}
}
}
void dfs2(int u, int p){
if(isX[u]){
dpX[u] = 0;
}
if(isY[u]){
dpY[u] = 0;
}
for(pair<int, long long> x : adj2[u]){
int v = x.first;
if(v != p){
dfs2(v, u);
ans = min(ans, dpX[u] + dpY[v] + x.second);
ans = min(ans, dpY[u] + dpX[v] + x.second);
dpX[u] = min(dpX[u], dpX[v] + x.second);
dpY[u] = min(dpY[u], dpY[v] + x.second);
}
}
}
int binjump(int x, int k){
int final = 0;
while(k > 0){
if(k % 2 == 1){
x = dp[final][x];
}
final++;
k >>= 1;
}
return x;
}
int lca(int a, int b){
if(level[a] > level[b]){
swap(a, b);
}
int difference = level[b] - level[a];
b = binjump(b, difference);
if(a == b){
return a;
}
for(int i = 20; i >= 0; i--){
if(dp[i][a] != dp[i][b]){
a = dp[i][a];
b = dp[i][b];
}
}
return dp[0][a];
}
void Init(int N, int A[], int B[], int D[]){
tin.resize(N);
adj.resize(N);
adj2.resize(N);
pref.resize(N);
dpX.resize(N);
dpY.resize(N);
isX.resize(N);
isY.resize(N);
level.resize(N);
for(int i = 0; i < N - 1; i++){
adj[A[i]].push_back(make_pair(B[i], D[i]));
adj[B[i]].push_back(make_pair(A[i], D[i]));
}
for(int j = 0; j < 21; j++){
dp[j].resize(N);
}
dfs(0, -1);
for(int i = 1; i < 21; i++){
for(int j = 0; j < N; j++){
dp[i][j] = dp[i - 1][dp[i - 1][j]];
}
}
}
long long Query(int S, int X[], int T, int Y[]){
vector<int> v;
for(int i = 0; i < S; i++){
v.push_back(X[i]);
isX[X[i]] = true;
}
for(int i = 0; i < T; i++){
v.push_back(Y[i]);
isY[Y[i]] = true;
}
sort(v.begin(), v.end(), sort_tin);
vector<int> nodes = v;
for(int i = 0; i + 1 < (int)v.size(); i++){
nodes.push_back(lca(v[i], v[i + 1]));
}
sort(nodes.begin(), nodes.end(), sort_tin);
nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());
for(int x : nodes){
adj2[x].clear();
dpX[x] = INF;
dpY[x] = INF;
}
vector<int> st;
st.push_back(nodes[0]);
for(int i = 1; i < (int)nodes.size(); i++){
while(!st.empty() && lca(st.back(), nodes[i]) != st.back()){
st.pop_back();
}
int p = st.back();
adj2[p].push_back(make_pair(nodes[i], pref[nodes[i]] - pref[p]));
adj2[nodes[i]].push_back(make_pair(p, pref[nodes[i]] - pref[p]));
st.push_back(nodes[i]);
}
ans = INF;
dfs2(nodes[0], -1);
for(int i = 0; i < S; i++){
isX[X[i]] = false;
}
for(int i = 0; i < T; i++){
isY[Y[i]] = false;
}
return ans;
}
// int main(){
// int N, Q;
// cin >> N >> Q;
// int A[N - 1];
// int B[N - 1];
// int D[N - 1];
// for(int i = 0; i < N - 1; i++){
// cin >> A[i] >> B[i] >> D[i];
// }
// Init(N, A, B, D);
// while(Q--){
// int S, T;
// cin >> S >> T;
// int X[S];
// for(int i = 0; i < S; i++){
// cin >> X[i];
// }
// int Y[T];
// for(int i = 0; i < T; i++){
// cin >> Y[i];
// }
// cout << Query(S, X, T, Y) << "\n";
// }
// }
