#include<bits/stdc++.h>
#define str string
#define task "strdel"
#define ii pair<int,int>
#define iii pair<int,ii>
#define iv pair<ii,ii>
#define se second
#define fi first
#define ffi fi.fi
#define sfi se.fi
#define sse se.se
#define fse fi.se
#define lt(i, c, d) for(int i = c; i <= d; ++i)
#define fl(i, c, d) for(int i = d; i >= c; --i)
#define pb push_back
#define emb emplace_back
#define emf emplace_front
#define em emplace
using namespace std;
const int N=1e6+5,lg=20,mod=1e9+7;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int u,int v){
return u+rd()%(v-u+1);
}
int n,k,sz[N],dp[N],ans=1e9;
vector<ii>a[N];
bool check[N];
void dfs(int u,int cha){
sz[u]=1;
for(ii v:a[u]){
if(v.fi==cha||check[v.fi])continue;
dfs(v.fi,u);
sz[u]+=sz[v.fi];
}
}
int fin(int u,int cha,int n){
for(ii v:a[u]){
if(v.fi!=cha&&!check[v.fi]&&sz[v.fi]>n/2)return fin(v.fi,u,n);
}
return u;
}
void add(int u,int cha,int sum,int canh){
// cout <<u<<" "<<canh<<" "<<sum<<" "<<dp[sum]<<'\n';
ans=min(ans,canh+dp[sum]);
for(ii v:a[u]){
if(v.fi==cha||check[v.fi]||sum-v.se<0)continue;
add(v.fi,u,sum-v.se,canh+1);
}
}
void them(int u,int cha,int sum,int canh){
dp[sum]=min(dp[sum],canh);
for(ii v:a[u]){
if(v.fi==cha||check[v.fi]||sum-v.se<0)continue;
them(v.fi,u,sum-v.se,canh+1);
}
}
void buildcen(int u,int cha){
dfs(u,-1);
int g=fin(u,-1,sz[u]);
// cout <<g<<'\n';
// for(int i=1;i<=n;++i)cout <<sz[i]<<" ";
for(ii v:a[g]){
if(v.fi==cha||check[v.fi])continue;
add(v.fi,u,k,1);
them(v.fi,u,k,1);
}
check[g]=true;
for(ii v:a[g]){
if(v.fi==cha||check[v.fi])continue;
buildcen(v.fi,g);
}
}
int best_path(int n,int k,int b[][2],int w[]){
// for(int i=1;i<n;++i)cin >> b[i].fi >> b[i].se;
for(int i=1;i<n;++i){
int u=b[i][1]+1,v=b[i][0]+1,w;
// cout <<u<<" "<<v<<" "<<w<<'\n';
a[u].emb(v,w[i]);
a[v].emb(u,w[i]);
}
for(int i=1;i<=k;++i)dp[i]=1e9;
buildcen(1,-1);
return (ans==1e9?-1:ans);
}
