#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,ll> pii;
typedef pair<ll,int> porra;
typedef pair<ll,ll> pll;
#define f first
#define s second
const int maxn = 5e5+10, maxl = 21;
const ll inf = 1e18;
vector<pii> tree[maxn], grafo[maxn];
int n, tt, in[maxn], tab[maxn][maxl], nivel[maxn], sz[maxn];
vector<int> limpa;
ll dist[maxn], ans;
bool red[maxn], blue[maxn], mark[maxn];
void dfs_lca(int u, int p = 0){
in[u] = tt++;
for(pii vv : tree[u]){
int v = vv.f;
ll d = vv.s;
if(v == p) continue;
nivel[v] = nivel[u] + 1;
dist[v] = dist[u] + d;
tab[v][0] = u;
dfs_lca(v, u);
}
}
int lca(int u, int v){
if(u == v) return u;
if(nivel[u] < nivel[v]) swap(u, v);
for(int i=maxl-1; i>=0; i--){
if(nivel[tab[u][i]] >= nivel[v]) u = tab[u][i];
}
if(u == v) return u;
for(int i=maxl-1; i>=0; i--){
if(tab[u][i] and tab[u][i] != tab[v][i]){
u = tab[u][i], v = tab[v][i];
}
}
return tab[u][0];
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for(int i=0; i<n-1; i++){
int u = A[i] + 1, v = B[i] + 1, d = D[i];
tree[u].push_back({v, d});
tree[v].push_back({u, d});
}
nivel[1] = 1;
dfs_lca(1);
for(int j=1; j<maxl; j++){
for(int i=1; i<=n; i++){
tab[i][j] = tab[tab[i][j-1]][j-1];
}
}
}
void virtual_tree(vector<int> &k){
auto comp = [&](int u, int v){
return in[u] < in[v];
};
sort(k.begin(), k.end(), comp);
int tam = k.size();
for(int i=1; i<tam; i++) k.push_back(lca(k[i-1], k[i]));
sort(k.begin(), k.end(), comp);
k.erase(unique(k.begin(), k.end()), k.end());
for(int i=0; i<k.size(); i++){
limpa.push_back(k[i]);
if(!i) continue;
int l = lca(k[i-1], k[i]);
ll w = dist[k[i]] - dist[l];
//cout << "adicionando aresta: " << l << " " << k[i] << " " << w << "\n";
grafo[l].push_back({k[i], w});
grafo[k[i]].push_back({l, w});
}
}
void dfs(int u, int p = 0){
sz[u] = 1;
for(pii vv : grafo[u]){
int v = vv.f;
if(v == p or mark[v]) continue;
dfs(v, u);
sz[u] += sz[v];
}
}
int centroid(int u, int siz, int p = 0){
for(pii vv : grafo[u]){
int v = vv.f;
if(v == p or mark[v]) continue;
if(sz[v] + sz[v] > siz) return centroid(v, siz, u);
}
return u;
}
pll aux;
void solve(int u, ll d, int p){
if(red[u]) aux.f = min(aux.f, d);
if(blue[u]) aux.s = min(aux.s, d);
for(pii vv : grafo[u]){
int v = vv.f;
ll dis = d + vv.s;
if(v == p or mark[v]) continue;
solve(v, dis, u);
}
}
void decompose(int u){
dfs(u);
int c = centroid(u, sz[u]);
mark[c] = 1;
porra mnblue[2], mnred[2];
for(int i=0; i<2; i++) mnblue[i] = mnred[i] = {inf, 0};
if(red[c]) mnred[0] = {0, -1};
if(blue[c]) mnblue[0] = {0, -1};
vector<array<ll,3>> wtf;
for(pii vv : grafo[c]){
int v = vv.f;
ll d = vv.s;
if(mark[v]) continue;
aux = {inf, inf};
solve(v, d, c);
if(aux.f <= mnred[0].f){
mnred[1] = mnred[0];
mnred[0] = {aux.f, v};
}
else if(aux.f <= mnred[1].f) mnred[1] = {aux.f, v};
if(aux.s <= mnblue[0].f){
mnblue[1] = mnblue[0];
mnblue[0] = {aux.s, v};
}
else if(aux.s <= mnblue[1].f) mnblue[1] = {aux.s, v};
wtf.push_back({v, aux.f, aux.s});
}
for(auto x : wtf){
ll u = x[0], r = x[1], b = x[2];
if(mnred[0].s == u) ans = min(ans, mnred[1].f + b);
else ans = min(ans, mnred[0].f + b);
if(mnblue[0].s == u) ans = min(ans, mnblue[1].f + r);
else ans = min(ans, mnblue[0].f + r);
}
for(pii viz : grafo[c]){
int v = viz.f;
if(mark[v]) continue;
decompose(v);
}
}
long long Query(int S, int X[], int T, int Y[]) {
vector<int> k;
for(int i=0; i<S; i++){
++X[i];
k.push_back(X[i]);
red[X[i]] = 1;
}
for(int i=0; i<T; i++){
++Y[i];
k.push_back(Y[i]);
blue[Y[i]] = 1;
}
virtual_tree(k);
ans = inf;
decompose(limpa[0]);
for(int i : limpa){
grafo[i].clear();
mark[i] = 0;
sz[i] = 0;
}
limpa.clear();
for(int i=0; i<S; i++) red[X[i]] = 0;
for(int i=0; i<T; i++) blue[Y[i]] = 0;
return ans;
}
