/*
* @Author: RMQuan
* @Date: 2025-10-22 12:01:01
* @Last Modified by: RMQuan
* @Last Modified time: 2025-10-22 12:43:43
*/
/*idea :
*/
#include <bits/stdc++.h>
bool M1;
#define ll long long
#define INTMAX INT_MAX
#define INTMIN INT_MIN
#define LONGMAX LLONG_MAX
#define LONGMIN LLONG_MIN
#define fi first
#define se second
#define memfull(a,b) memset(a,b,sizeof(a));
#define endl '\n'
#define TASK "TEST"
#define file() if (fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin); freopen(TASK".out","w",stdout);}
using namespace std;
const int MOD=1e9+7;
const int maxn=5e5+7;
const int LOG=20;
const int inf=1e9;
vector<pair<int,int> > adj[maxn];
int n,q,rmq[2*maxn][LOG+1],pos[maxn],id_rmq=0,h[maxn],depth[maxn],sz[maxn];
bool is_deleted[maxn];
int mn_dis[maxn];
vector<pair<int,int> > centroid_root[maxn];
void dfs(int u,int p)
{
pos[u]=++id_rmq;
rmq[id_rmq][0]=u;
for (auto v:adj[u])
{
if (v.fi==p)continue;
h[v.fi]=h[u]+1;
depth[v.fi]=h[u]+v.se;
dfs(v.fi,u);
rmq[++id_rmq][0]=u;
}
}
int get_min(int u,int v)
{
return (h[u]<h[v]?u:v);
}
int lca(int u,int v)
{
int L=pos[u];
int R=pos[v];
if (L>R)swap(u,v);
int k=__lg(R-L+1);
return get_min(rmq[L][k],rmq[R-(1<<k)+1][k]);
}
void prepare()
{
for (int j=1;j<=LOG;j++)
{
for (int i=1;i<=id_rmq;i++)rmq[i][j]=get_min(rmq[i][j-1],rmq[i+(1<<(j-1))][j-1]);
}
}
void pre_dfs(int u,int p)
{
sz[u]=1;
for (auto v:adj[u])
{
if (v.fi==p||is_deleted[v.fi])continue;
pre_dfs(v.fi,u);
sz[u]+=sz[v.fi];
}
}
int find_centroid(int u,int p,int N)
{
for (auto v:adj[u])
{
if (v.fi==p||is_deleted[v.fi])continue;
if (sz[v.fi]>=N)return find_centroid(v.fi,u,N);
}
return u;
}
void cal(int u,int p,int w,int root)
{
centroid_root[u].push_back({root,w});
for (auto v:adj[u])
{
if (v.fi==p||is_deleted[v.fi])continue;
cal(v.fi,u,w+v.se,root);
}
}
void decomposition(int u)
{
pre_dfs(u,0);
int N=sz[u];
int root=find_centroid(u,0,N/2);
is_deleted[root]=true;
centroid_root[root].push_back({root,0});
for (auto v:adj[root])
{
if (!is_deleted[v.fi])cal(v.fi,root,v.se,root);
}
for (auto v:adj[root])if (!is_deleted[v.fi])decomposition(v.fi);
}
void solve()
{
int N,M;
cin>>N>>M;
}
void Init(int N, int A[], int B[], int D[])
{
n=N;
for (int i=0;i<=N-2;i++)
{
int x=A[i]+1;
int y=B[i]+1;
int w=D[i];
adj[x].push_back({y,w});
adj[y].push_back({x,w});
}
decomposition(1);
for (int i=1;i<=n;i++)mn_dis[i]=inf;
}
long long Query(int S, int X[], int T, int Y[])
{
vector<int> s;
vector<int> t;
for (int i=0;i<S;i++)s.push_back(X[i]+1);
for (int i=0;i<T;i++)t.push_back(Y[i]+1);
int ans=inf;
for (auto i:s)
{
for (auto j:centroid_root[i])mn_dis[j.fi]=min(mn_dis[j.fi],j.se);
}
for (auto i:t)
{
for (auto j:centroid_root[i])ans=min(ans,mn_dis[j.fi]+j.se);
}
for (auto i:s)
{
for (auto j:centroid_root[i])mn_dis[j.fi]=inf;
}
return ans;
}
