#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
#define pb push_back
#define mp make_pair
const int NN = 5e5+7;
vector <vector <pii>> graph(NN);
vector <vector <int>> up(NN);
vector <int> tin(NN), tout(NN), saizu(NN), par(NN), vis(NN);
vector <ll> ans(NN, 2e18), dist(NN);
int timer;
stack <int> st;
void dfs(int v, int p = 0){
tin[v] = ++timer;
up[v][0] = p;
for(int i = 1; i < 20; i++){
up[v][i] = up[up[v][i-1]][i-1];
}
for(auto to : graph[v]){
if(to.first != p){
dist[to.first] = dist[v]+to.second;
dfs(to.first, v);
}
}
tout[v] = ++timer;
}
bool upper(int a, int b){
return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int lca(int a, int b){
if(upper(a, b)) return a;
if(upper(b, a)) return b;
for(int i = 19; i >= 0; i--){
if(!upper(up[a][i], b)){
a = up[a][i];
}
}
return up[a][0];
}
ll getdist(int a, int b){
return dist[a]+dist[b]-2*dist[lca(a, b)];
}
void find_size(int v, int p = -1){
saizu[v] = 1;
for(auto to : graph[v]){
if(!vis[to.first] && to.first != p){
find_size(to.first, v);
saizu[v] += saizu[to.first];
}
}
}
int find_centroid(int v, int p, int n){
for(auto to : graph[v]){
if(!vis[to.first] && to.first != p && saizu[to.first] > n/2){
return find_centroid(to.first, v, n);
}
}
return v;
}
void init_centroid(int v = 0, int p = -1){
find_size(v);
int c = find_centroid(v, p, saizu[v]);
vis[c] = 1;
par[c] = p;
for(auto to : graph[c]){
if(!vis[to.first]){
init_centroid(to.first, c);
}
}
vis[c] = 0;
}
void Init(int n, int x[], int y[], int w[]){
int i;
for(i = 0; i < n; i++){
up[i].resize(20);
}
for(i = 0; i < n-1; i++){
graph[x[i]].pb(mp(y[i], w[i]));
graph[y[i]].pb(mp(x[i], w[i]));
}
dfs(0);
init_centroid();
}
void update(int v){
int x = v;
while(x != -1){
ans[x] = min(ans[x], getdist(x, v));
st.push(x);
x = par[x];
}
}
ll get(int v){
ll x = v, mn = 2e18;
while(x != -1){
mn = min(ans[x]+getdist(x, v), mn);
x = par[x];
}
return mn;
}
long long Query(int s, int x[], int t, int y[]){
int i;
for(i = 0; i < s; i++){
update(x[i]);
}
ll mn = 2e18;
for(i = 0; i < t; i++){
mn = min(mn, get(y[i]));
}
while(st.size()){
ans[st.top()] = 2e18;
st.pop();
}
return mn;
}
