#include<bits/stdc++.h>
#include "factories.h"
using namespace std;
// define
#define execute cerr << " Time: " << fixed << setprecision(6) << (1.0 * clock() / CLOCKS_PER_SEC) << "s\n";
#define ll long long
#define ii pair <int , ll>
#define iii pair <int , ii>
#define se second
#define fi first
#define all(v) (v).begin() , (v).end()
#define Unique(v) sort(all(v)) , v.resize(unique(all(v)) - v.begin())
#define bit(x,i) (((x) >> (i)) & 1LL)
#define flip(x,i) ((x) ^ (1LL << (i)))
#define ms(d,x) memset(d , x , sizeof(d))
#define exist __exist
#define ends __ends
#define visit visited
#define left __left
#define right __right
#define prev __prev
#define next __next
#define sitingfake 1
#define orz 1
//constant
const long long mod = 1e9 + 7;
const long long linf = 4557430888798830399LL;
const long long nlinf = -4485090715960753727LL;
const int LOG = 20;
const int inf = 1061109567;
const int ninf = -1044266559;
const int dx[] = {0 , -1 , 0 , 1};
const int dy[] = {-1 , 0 , 1 , 0};
template<typename T> bool maximize(T &a, const T &b)
{
if(a < b) {a = b; return 1;}
return 0;
}
template<typename T> bool minimize(T &a, const T &b)
{
if(a > b) {a = b; return 1;}
return 0;
}
void Plus(ll & a ,ll b)
{
b %= mod;
a += b;
if(a < 0) a += mod;
a %= mod;
return;
}
void Mul(ll & a, ll b)
{
(a *= (b % mod)) %= mod;
return;
}
//code
const int maxn = 5e5 + 7;
vector <ii> adj[maxn];
int par[maxn];
ll pathLength[maxn] , Min[maxn];
bool isc[maxn];
int sz[maxn] , n;
int in[maxn] , out[maxn] , depth[maxn] ,timer;
int arr[maxn * 2][21];
void dfs(int u , int p)
{
in[u] = ++timer;
arr[timer][0] = u;
for(auto &[v , w]: adj[u])
{
if(v != p)
{
depth[v] = depth[u] + 1;
pathLength[v] = pathLength[u] + w;
dfs(v , u);
arr[++timer][0] = u;
}
}
out[u] = timer;
}
void BuildLca()
{
for(int j = 1; (1 << j) <= timer ; j++)
{
for(int i = 1; i + (1 << j) - 1 <= timer ; i++)
{
arr[i][j] = (depth[arr[i][j - 1]] < depth[arr[i + (1 << (j - 1))][j - 1]])
? arr[i][j - 1] : arr[i + (1 << (j - 1))][j - 1];
}
}
}
int lca(int u , int v)
{
int l = in[u] , r = in[v];
if(l > r) swap(l , r);
int k = __lg(r - l + 1);
if(depth[arr[l][k]] < depth[arr[r - (1 << k) + 1][k]])
{
return arr[l][k];
}
return arr[r - (1 << k) + 1][k];
}
ll dist(int u ,int v)
{
return pathLength[u] + pathLength[v] - 2 * pathLength[lca(u ,v)];
}
void dfscount(int u , int p)
{
sz[u] = 1;
for(auto &[v , w] : adj[u])
{
if(v != p && !isc[v])
{
dfscount(v , u);
sz[u] += sz[v];
}
}
}
int centroid(int u , int p , int Size)
{
for(auto &[v , w] : adj[u])
{
if(v != p && !isc[v] && sz[v] > Size / 2)
{
return centroid(v , u , Size);
}
}
return u;
}
void cd(int u , int p)
{
dfscount(u , -1);
int c = centroid(u , -1 , sz[u]);
isc[c] = 1;
par[c] = p;
for(auto &[v , w] : adj[c])
{
if(!isc[v])
{
cd(v , c);
}
}
}
void Add(int u)
{
int cur = u;
while(cur != -1)
{
Min[cur] = min(Min[cur] , dist(u , cur));
cur = par[cur];
}
}
ll compute(int u)
{
ll ans = linf;
int cur = u;
while(cur != -1)
{
ans = min(ans , Min[cur] + dist(u , cur));
cur = par[cur];
}
return ans;
}
void Reset(int u)
{
while(u != -1)
{
Min[u] = linf;
u = par[u];
}
}
void Init(int N , int A[] , int B[] , int D[])
{
n = N;
for(int i = 0; i < n - 1; i++)
{
int u = A[i] , v = B[i] , d = D[i];
adj[u].push_back({v , d});
adj[v].push_back({u , d});
}
dfs(0 , -1);
BuildLca();
cd(0 , -1);
ms(Min , 0x3f);
}
ll Query(int S , int X[] , int T , int Y[])
{
for(int i = 0; i < S; i++)
{
Add(X[i]);
}
ll ans = linf;
for(int i = 0; i < T; i++)
{
ans = min(ans , compute(Y[i]));
}
for(int i = 0; i < S; i++)
{
Reset(X[i]);
}
return ans;
}
