#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>> graph[500005];
bool vis[500005];
int depth[500005], parent[500005], jump[500005][20];
long long dist[500005][20];
void dfs(int node) {
vis[node]=true;
for (auto x : graph[node]) {
if (! vis[x.first]) {
depth[x.first]=depth[node]+1;
parent[x.first]=node;
jump[x.first][0]=node;
dist[x.first][0]=x.second;
dfs(x.first);
}
}
}
void Init(int N, int A[], int B[], int D[]) {
for (int i = 0; i < N-1; i++) {
graph[A[i]].push_back({B[i], D[i]});
graph[B[i]].push_back({A[i], D[i]});
}
depth[0]=0;
parent[0]=0;
jump[0][0]=0;
dist[0][0]=0;
dfs(0);
for (int j = 1; j <= 19; j++) {
for (int i = 0; i < N; i++) {
jump[i][j]=jump[jump[i][j-1]][j-1];
dist[i][j]=dist[i][j-1]+dist[jump[i][j-1]][j-1];
//cout << dist[i][0] << " ";
}
//cout << "\n";
}
}
long long Query(int S, int X[], int T, int Y[]) {
long long mindist=1e18;
for (int i = 0; i < S; i++) {
for (int j = 0; j < T; j++) {
int u=X[i], v=Y[j];
long long d=0;
if (depth[u] < depth[v]) swap(u, v);
for (int i = 19; i >= 0; i--) {
if (depth[jump[u][i]] >= depth[v]) {
d += dist[u][i];
u = jump[u][i];
}
}
if (u != v) {
for (int i = 19; i >= 0; i--) {
if (jump[u][i] != jump[v][i]) {
d += dist[u][i];
d += dist[v][i];
u=jump[u][i];
v=jump[v][i];
}
}
d += dist[u][0]+dist[v][0];
}
mindist=min(mindist, d);
}
}
return mindist;
}
