#include <bits/stdc++.h>
bool M1;
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define memfull(a,b) memset(a,b,sizeof(a));
#define file(a) freopen(a".inp","r",stdin); freopen(a".out","w",stdout);
using namespace std;
const ll MOD=1e9+7;
const ll maxn=1e6+7;
ll sz[maxn];
bool is_deleted[maxn];
vector<pair<ll,ll> > adj[maxn];
ll n,k,cnt[maxn],ans=1e18;
void cal_sz(ll u,ll p)
{
sz[u]=1;
for (auto v:adj[u])
{
if (v.fi==p||is_deleted[v.fi])continue;
cal_sz(v.fi,u);
sz[u]+=sz[v.fi];
}
}
ll find_centroid(ll u,ll p,ll N)
{
for (auto v:adj[u])
{
if (v.fi!=p&&!is_deleted[v.fi]&&sz[v.fi]>N)return find_centroid(v.fi,u,N);
}
return u;
}
void cal(ll u,ll p,ll w,ll type,ll h)
{
if (w>k)return ;
if (type==1)ans=min(ans,cnt[k-w]+h);
else if (type==0)cnt[w]=min(cnt[w],h);
else if (type==-1)cnt[w]=1e18;
for (auto v:adj[u])
{
if (v.fi==p||is_deleted[v.fi])continue;
cal(v.fi,u,w+v.se,type,h+1);
}
}
void centroid_decomposition(ll u)
{
cal_sz(u,0);
ll N=sz[u];
ll root=find_centroid(u,0,N/2);
is_deleted[root]=true;
cnt[0]=0;
for (auto v:adj[root])
{
if (!is_deleted[v.fi])
{
cal(v.fi,root,v.se,1,1);
cal(v.fi,root,v.se,0,1);
}
}
cnt[0]=1e18;
for (auto v:adj[root])
{
if (!is_deleted[v.fi])
{
cal(v.fi,root,v.se,-1,1);
}
}
for (auto v:adj[root])if (!is_deleted[v.fi])centroid_decomposition(v.fi);
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N, k = K;
for (int i=0;i<n;i++){
adj[H[i][0]+1].push_back({H[i][1]+1,L[i] });
adj[H[i][1]+1].push_back({H[i][0]+1,L[i]});
}
for (int i=0;i<=k;i++)cnt[i]=1e18;
centroid_decomposition(1);
return (ans==1e18?-1:ans);
}
