#include "factories.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 500005;
template<class T, int SZ> struct RMQ {
T stor[SZ][32-__builtin_clz(SZ)];
T comb(T a, T b) {
return min(a,b);
}
void build(vector<T>& x) {
F0R(i,sz(x)) stor[i][0] = x[i];
FOR(j,1,32-__builtin_clz(SZ)) F0R(i,SZ-(1<<(j-1)))
stor[i][j] = comb(stor[i][j-1],
stor[i+(1<<(j-1))][j-1]);
}
T query(int l, int r) {
int x = 31-__builtin_clz(r-l+1);
return comb(stor[l][x],stor[r-(1<<x)+1][x]);
}
};
template<int SZ> struct LCA {
vpi edges[SZ];
RMQ<pl,2*SZ> r;
vpl tmp;
ll depth[SZ];
int pos[SZ];
int V, R;
void addEdge(int u, int v, int d) {
edges[u].pb({v,d}), edges[v].pb({u,d});
}
void dfs(int u, int prev){
pos[u] = sz(tmp);
tmp.pb({depth[u],u});
for (pi v: edges[u]) if (v.f != prev) {
depth[v.f] = depth[u]+v.s;
dfs(v.f, u);
tmp.pb({depth[u],u});
}
}
void construct() {
dfs(R, 0);
r.build(tmp);
}
int lca(int u, int v){
u = pos[u], v = pos[v];
if (u > v) swap(u,v);
return r.query(u,v).s;
}
ll dist(int u, int v) {
return depth[u]+depth[v]-2*depth[lca(u,v)];
}
};
LCA<MX> L;
template<int SZ> struct Dijkstra {
ll dist[SZ];
vector<pi> adj[SZ];
void addEdge(int a, int b, int d) {
adj[a].pb({b,d}), adj[b].pb({a,d});
}
void gen(int S, int X[]) {
F0R(i,L.V) dist[i] = INF;
priority_queue<pl,vector<pl>,greater<pl>> q;
F0R(i,S) {
dist[X[i]] = 0;
q.push({0,X[i]});
}
while (q.size()) {
pl x = q.top(); q.pop();
if (dist[x.s] < x.f) continue;
for (pi y: adj[x.s]) if (x.f+y.s < dist[y.f]) {
dist[y.f] = x.f+y.s;
q.push({dist[y.f],y.f});
}
}
}
};
Dijkstra<MX> Di;
void Init(int N, int A[], int B[], int D[]) {
L.V = N, L.R = 0;
F0R(i,N-1) {
L.addEdge(A[i],B[i],D[i]);
Di.addEdge(A[i],B[i],D[i]);
}
L.construct();
}
long long Query(int S, int X[], int T, int Y[]) {
ll ans = INF;
if ((ll)S*T > L.V) {
Di.gen(S,X);
F0R(i,T) ans = min(ans,Di.dist[Y[i]]);
} else {
F0R(i,S) F0R(j,T) ans = min(ans,L.dist(X[i],Y[j]));
}
return ans;
}
