#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define INF 0x3f3f3f3f
#define LLINF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
typedef pair<int, int> pii;
#define ms(x, y) memset(x, y, sizeof(x))
#define pb push_back
#define f first
#define s second
const int mod = 1e9 + 7, base = 131, MM = 5e5 + 5, LG = 25;
int n, dep[MM], w[MM], pre[MM]; bool vis[MM];
ll dist[LG][MM], ans[MM];
vector<pii> adj[MM]; vector<int> clr;
void get_weight(int src, int par){
w[src] = 1;
for (auto v : adj[src]){
if (v.s == par || vis[v.s]) continue;
get_weight(v.s, src);
w[src] += w[v.s];
}
}
int get_cent(int src, int par, int wt){
for (auto v : adj[src])
if (v.s != par && !vis[v.s] && w[v.s] * 2 > wt)
return get_cent(v.s, src, wt);
return src;
}
void dfs(int src, int par, ll d, int lvl){
dist[lvl][src] = d;
for (auto v : adj[src]){
if (v.s == par || vis[v.s]) continue;
dfs(v.s, src, d + v.f, lvl);
}
}
void decomp(int src, int lvl){
dfs(src, src, 0, lvl);
vis[src] = 1;
for (auto v : adj[src]){
if (vis[v.s]) continue;
get_weight(v.s, src);
int rt = get_cent(v.s, src, w[v.s]);
pre[rt] = src, dep[rt] = lvl + 1;
decomp(rt, lvl + 1);
}
}
void Init(int N, int A[], int B[], int D[]){
n = N;
for (int i = 0; i < N - 1; i++){
A[i]++, B[i]++;
adj[A[i]].pb({D[i], B[i]});
adj[B[i]].pb({D[i], A[i]});
}
get_weight(1, 1);
decomp(get_cent(1, 1, N), 0);
ms(ans, INF);
}
long long Query(int S, int X[], int T, int Y[]){
for (int i = 0; i < S; i++)
for (int src = X[i] + 1, l = dep[src], tmp = src; l >= 0; l--, tmp = pre[tmp]){
if (ans[tmp] == LLINF) clr.pb(tmp);
ans[tmp] = min(ans[tmp], dist[l][src]);
}
ll ret = LLINF;
for (int i = 0; i < T; i++)
for (int src = Y[i] + 1, l = dep[src], tmp = src; l >= 0; l--, tmp = pre[tmp])
ret = min(ret, dist[l][src] + ans[tmp]);
for (int p : clr) ans[p] = LLINF;
clr.clear();
return ret;
}
