#include"factories.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define f first
#define s second
// global
int n;
vector<pair<int,long long> > v[500005];
// lca
int deep[500005],spa[500005][20];
long long dist[500005][20];
void lca_dfs(int nw,int fa)
{
for(auto go: v[nw])
{
if(go.f != fa)
{
deep[go.f] = deep[nw] + 1;
spa[go.f][0] = nw;
dist[go.f][0] = go.s;
lca_dfs(go.f, nw);
}
}
}
void lca_init()
{
memset(spa,-1,sizeof(spa));
memset(dist,-1,sizeof(dist));
deep[0] = 0;
spa[0][0] = -1;
dist[0][0] = -1;
lca_dfs(0, -1);
for(int j = 1; j < 20; j++)
{
for(int i = 0; i < n; i++)
{
if(spa[i][j - 1] == -1)
continue;
spa[i][j] = spa[spa[i][j - 1]][j - 1];
dist[i][j] = dist[i][j - 1] + dist[spa[i][j - 1]][j - 1];
}
}
}
long long lca_query(int a,int b)
{
long long ret = 0;
if(deep[a] > deep[b]) swap(a,b);
int diff = deep[b] - deep[a];
for(int i = 0; i < 20; i++)
if((1<<i)&diff)
{
ret += dist[b][i];
b = spa[b][i];
}
if(a==b)
return ret;
for(int i = 19; i >= 0; i--)
{
if(spa[a][i] != spa[b][i])
{
ret += dist[a][i] + dist[b][i];
a = spa[a][i];
b = spa[b][i];
}
}
return ret + dist[a][0] + dist[b][0];
}
// centroid
int cen[500005],sz[500005];
long long mn[500005];
int re_size(int nw,int fa)
{
sz[nw] = 1;
for(auto go: v[nw])
if(go.f != fa && cen[go.f] == -1)
sz[nw] += re_size(go.f,nw);
return sz[nw];
}
int fi_cen(int nw,int fa,int sum)
{
for(auto go: v[nw])
if(go.f != fa && cen[go.f] == -1 && sz[go.f] > sum / 2)
return fi_cen(go.f,nw,sum);
return nw;
}
void centroid_decomp(int nw,int fa)
{
int c = fi_cen(nw, -1, re_size(nw, -1));
if(fa == -1) fa = c;
cen[c] = fa;
for(auto go: v[c])
if(go.f != fa && cen[go.f] == -1)
centroid_decomp(go.f, c);
}
void cen_upd(int cur,int st)
{
mn[cur] = min(mn[cur],lca_query(st,cur));
if(cen[cur] == cur) return ;
cen_upd(cen[cur],st);
}
long long cen_query(int cur,int st)
{
long long ret = 1e18;
ret = min(ret,mn[cur] + lca_query(st,cur));
if(cen[cur] == cur) return ret;
return min(ret,cen_query(cen[cur],st));
}
void Init(int N, int A[], int B[], int D[])
{
n = N;
for(int i = 0; i < n - 1; i++)
{
v[A[i]].pb({B[i],D[i]});
v[B[i]].pb({A[i],D[i]});
}
memset(cen,-1,sizeof(cen));
centroid_decomp(0, -1);
lca_init();
return ;
}
long long Query(int S, int X[], int T, int Y[])
{
long long ret = 1e18;
for(int i = 0; i < n; i++)
mn[i] = 1e18;
for(int i = 0; i < S; i++)
cen_upd(X[i],X[i]);
for(int i = 0; i < T; i++)
ret = min(ret,cen_query(Y[i],Y[i]));
return ret;
}
// int a[500005],b[500005],c[500005];
// int ps[500005],pt[500005];
// int main()
// {
// int n,q;
// scanf("%d %d",&n,&q);
// for(int i = 0; i < n - 1; i++)
// {
// scanf("%d %d %d",&a[i],&b[i],&c[i]);
// }
// Init(n, a, b, c);
// for(int i = 0; i < q; i++)
// {
// int s,t;
// scanf("%d %d",&s,&t);
// for(int j = 0; j < s; j++)
// scanf("%d",&ps[j]);
// for(int j = 0; j < t; j++)
// scanf("%d",&pt[j]);
// printf("%lld\n",Query(s, ps, t, pt));
// }
// return 0;
// }
