#include<bits/stdc++.h>
using namespace std;
#define task "task"
#define ii pair<int,int>
#define fi first
#define se second
//#define int long long
#define ll long long
#define ld double
#define mp make_pair
#define lg2 20
#define iii pair<int,ii>
#define iiii pair<ii,ii>
#define fii fi.fi
#define fis fi.se3
#define sfi se.fi
#define see se.se
#define base 29
int dx[]={0LL,0LL,1,-1,1,1,-1,-1};
int dy[]={1,-1,0LL,0LL,1,-1,1,-1};
const int maxn=1e6+5;
const int mod=1e9+7;
int n,root,sz[maxn],h[maxn],q,par[maxn],ans=2e9,mn[maxn],mx_h,k;
bool is_centroid[maxn];
vector<ii>a[maxn];
void dfs(int u,int cha)
{
sz[u]=1;
for(ii v:a[u])
{
if(v.fi==cha||is_centroid[v.fi])continue;
dfs(v.fi,u);
sz[u]+=sz[v.fi];
}
}
int find_centroid(int u,int tree_sz,int cha)
{
for(ii v:a[u])
if(v.fi!=cha&&!is_centroid[v.fi]&&sz[v.fi]>tree_sz/2) return find_centroid(v.fi,tree_sz,u);
return u;
}
void get(int u,int cha,int h,int w,int t)
{
if(w>k)return;
if(t==0)
ans=min(ans,mn[k-w]+h);
else mn[w]=min(mn[w],h);
mx_h=max(mx_h,w);
for(ii v:a[u])
{
if(v.fi==cha||is_centroid[v.fi])continue;
get(v.fi,u,h+1,w+v.se,t);
}
}
void build_centroid(int u,int pre_centroid)
{
dfs(u,-1);
int centroid=find_centroid(u,sz[u],-1);
if(root==0)root=centroid;
mx_h=0;
is_centroid[centroid]=true;
for(ii v:a[centroid])
{
if(!is_centroid[v.fi])
{
get(v.fi,centroid,1,v.se,0);
get(v.fi,centroid,1,v.se,1);
}
}
for(int i=1;i<=mx_h;i++)mn[i]=2e9;
for(ii v:a[centroid])
{
if(!is_centroid[v.fi])build_centroid(v.fi,centroid);
}
}
int best_path(int N,int K,int H[][2],int w[])
{
k=K,n=N;
for(int i=0;i<n-1;i++)
{
a[H[i][0]+1].push_back({H[i][1]+1,w[i]});
a[H[i][1]+1].push_back({H[i][0]+1,w[i]});
}
for(int i=0;i<=k;i++)mn[i]=2e9;
ans=2e9;
mn[0]=0;
build_centroid(1,-1);
if(ans>=2e9)return -1;
else return ans;
}
