// #pragma GCC optimize("O3")
// #pragma GCC optimization("Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
// #define ll long long
#define ll long long
#define FOR(i, l, r) for (ll i = (l); i <= (r); i++)
#define FOD(i, r, l) for (ll i = (r); i >= (l); i--)
#define fi first
#define se second
#define pii pair<ll, ll>
const ll mod = 1e9 + 7;
const ll MAXN = 5e5 + 5;
const ll oo = 1e18+7;
const ll base = 0;
ll n, qq;
vector<pii> adj[MAXN];
ll d[MAXN], up[MAXN][20], h[MAXN], in[MAXN], out[MAXN], cnt;
void dfs(ll u, ll p){
in[u]=out[u]=++cnt;
for(auto [v, w]:adj[u]){
if(v==p) continue;
d[v]=d[u]+w;
h[v]=h[u]+1;
up[v][0]=u;
FOR(i, 1, 19){
up[v][i]=up[up[v][i-1]][i-1];
}
dfs(v, u);
out[u]=max(out[u], out[v]);
}
}
ll lca(ll u, ll v){
if(h[u]!=h[v]){
if(h[u]<h[v]) swap(u, v);
ll k=h[u]-h[v];
FOR(i, 0, 19){
if((k>>i)&1){
u=up[u][i];
}
}
}
if(u==v) return u;
FOD(i, 19, 0){
if(up[u][i]!=up[v][i]){
u=up[u][i];
v=up[v][i];
}
}
return up[u][0];
}
ll dist(ll u, ll v){
return d[u]+d[v]-2*d[lca(u, v)];
}
bool cmp(ll u, ll v){
return in[u]<in[v];
}
bool inside(ll u, ll v){
if(in[u]<=in[v] && out[u]>=out[v]){
return 1;
}
return 0;
}
vector<pii> adj1[MAXN];
ll f[MAXN];
void dijsktra(vector<ll> &a, vector<ll> &b){
priority_queue<pii, vector<pii>, greater<pii>> q;
for(auto x:b){
f[x]=oo;
}
for(auto x:a){
f[x]=0;
q.push({0, x});
}
while(!q.empty()){
auto [c, u]=q.top();
q.pop();
if(c>f[u]) continue;
for(auto [v, w]:adj1[u]){
if(f[v]>f[u]+w){
f[v]=f[u]+w;
q.push({f[v], v});
}
}
}
}
ll solve(ll p, ll q, vector<ll> &a, vector<ll> &b){
vector<ll> vec;
for(auto x:a){
vec.push_back(x);
}
for(auto x:b){
vec.push_back(x);
}
sort(vec.begin(), vec.end(), cmp);
FOR(i, 1, p+q-1){
vec.push_back(lca(vec[i], vec[i-1]));
}
sort(vec.begin(), vec.end(), cmp);
vec.erase(unique(vec.begin(), vec.end()), vec.end());
stack<ll> st;
st.push(vec[0]);
// cout << vec[0] << ' ';
FOR(i, 1, vec.size()-1){
while(!inside(st.top(), vec[i])){
st.pop();
}
adj1[st.top()].push_back({vec[i], dist(st.top(), vec[i])});
adj1[vec[i]].push_back({st.top(), dist(st.top(), vec[i])});
// cout << st.top() << ' ' << vec[i] << ' ' << dist(st.top(), vec[i]) << '\n';
st.push(vec[i]);
// cout << vec[i] << ' ';
}
dijsktra(a, vec);
ll ans=oo;
for(auto x:b){
ans=min(ans, f[x]);
}
for(auto x:vec){
adj1[x].clear();
}
return ans;
}
void Init(int N, int A[], int B[], int D[]){
n=N;
FOR(i, 0, n-1){
adj[i].clear();
}
FOR(i, 0, n-2){
ll u, v, c;
u=A[i], v=B[i], c=D[i];
adj[u].push_back({v, c});
adj[v].push_back({u, c});
}
cnt=0;
dfs(0, -1);
return;
}
long long Query(int S, int X[], int T, int Y[]){
ll p=S, q=T;
vector<ll> a, b;
FOR(i, 0, S-1){
a.push_back(X[i]);
}
FOR(i, 0, T-1){
b.push_back(Y[i]);
}
return solve(p, q, a, b);
}
