#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3")
using namespace std;
using namespace __gnu_pbds;
#define pb push_back
#define ppb pop_back
#define all(x) (x).begin(),(x).end()
#define sz(x) int((x).size())
#define MEM(x, v) memset(x, v, sizeof(x))
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
template<typename T> using reverse_pq = priority_queue<T, vector<T>, greater<T>>;
template<typename T, typename CMP> using ordered_set = tree<T, null_type, CMP, rb_tree_tag, tree_order_statistics_node_update>;
void si() {}
template<typename T, typename... U>
void si(T& x, U&... u) {char _;int neg=1;do{while((x=getchar())<'0'&&(x!='-')){};if(x=='-'){neg=-1;x=getchar();}for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0);x*=neg;si(u...);}
template<typename T, typename U> typename common_type<T, U>::type min(T a, U b) { return (((a) < (b)) ? (a) : (b)); }
template<typename T, typename U> typename common_type<T, U>::type max(T a, U b) { return (((a) > (b)) ? (a) : (b)); }
template<typename T, typename U> typename common_type<T, U>::type minv(T a, U b) { return min(a, b); }
template<typename T, typename... U> typename common_type<T, U...>::type minv(T a, U... b) { return min(a, minv(b...)); }
template<typename T, typename U> typename common_type<T, U>::type maxv(T a, U b) { return max(a, b); }
template<typename T, typename... U> typename common_type<T, U...>::type maxv(T a, U... b) { return max(a, maxv(b...)); }
int lg2(long long x) { return 63 - __builtin_clzll(x); }
int lg2(int x) { return 31 - __builtin_clz(x); }
mt19937 rng(uint64_t(new char)+chrono::steady_clock::now().time_since_epoch().count());
const ll MOD = 1e9+7;
const ll HASH = 131;
const int MM = 5e5+5;
int n;
vector<pii> adj[MM];
vi s(MM);
vector<bool> vis(MM);
void dfs1(int u, int p) {
s[u] = 1;
for (auto [v,w] : adj[u]) {
if (v != p && !vis[v]) {
dfs1(v,u);
s[u] += s[v];
}
}
}
int centroid(int u, int p, int x) {
for (auto [v,w] : adj[u]) {
if (!vis[v] && v != p && s[v]*2 > x) return centroid(v,u,x);
}
return u;
}
vl dep[MM];
void dfs2(int u, int p, ll d) {
dep[u].pb(d);
for (auto [v,w] : adj[u]) {
if (v != p && !vis[v]) {
dfs2(v, u, d+w);
}
}
}
vi par(MM,-1);
void search(int u, int p) {
dfs1(u,p);
u = centroid(u,-1,s[u]);
par[u] = p;
vis[u] = 1;
dfs2(u,p,0);
for (auto [v,w] : adj[u]) {
if (!vis[v]) {
search(v,u);
}
}
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for (int i = 0; i < N-1; i++) {
adj[A[i]].pb({B[i],D[i]});
adj[B[i]].pb({A[i],D[i]});
// cout << A[i] << " " << B[i] << " " << D[i] << "\n";
}
search(0,-1);
// fill(vis.begin(), vis.begin()+N,0);
// fill(all(vis),0);
}
vl res(MM, LINF);
ll Query(int s, int x[], int t, int y[]) {
ll ans = LINF;
for (int i = 0; i < s; i++) for (int j = x[i]; j != -1; j = par[j]) res[j] = LINF;
for (int i = 0; i < s; i++) {
for (int j = x[i], pos = sz(dep[x[i]])-1; j != -1; j = par[j], pos--) {
res[j] = min(res[j], dep[x[i]][pos]);
}
}
for (int i = 0; i < t; i++) {
for (int j = y[i], pos = sz(dep[y[i]])-1; j != -1; j = par[j], pos--) {
ans = min(ans, res[j]+dep[y[i]][pos]);
}
}
return ans;
}
