#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#define ll long long
#define endl "\n"
#define inf LLONG_MAX
#define vll vector<ll>
#define sd second
#define ft first
#define al(x) x.begin(),x.end()
#define alr(x) x.rbegin(),x.rend()
#define pll pair<ll, ll>
#define mod 1000000007
#define _set tree<pll, null_type, less<pll>, rb_tree_tag, tree_order_statistics_node_update>
using namespace std;
using namespace __gnu_pbds;
vector<vector<pair<ll, ll>>> adj;
vector<ll> v;
vector<bool>visited;
inline ll dfs(ll n, ll p){
v[n]=1;
for(auto& [y, w]: adj[n]){
if(y==p || visited[y]==1)continue;
v[n]+=dfs(y, n);
}
return v[n];
}
inline ll _find(ll n, ll n1, ll p){
for(auto& [y, w]: adj[n]){
if(y==p)continue;
if(v[y]>n1/2 && !visited[y])return _find(y, n1, n);
}
return n;
}
map<ll, ll> m;
vector<ll> v3;
vector<pair<ll, ll>> v2;
ll cnt=0, lim, cnt1=0, cnt3=0, res=LLONG_MAX;
inline void dfs1(ll n, ll p){
// cout<<n<<" "<<cnt3<<" "<<cnt<<endl;
if(cnt<=lim)v2.push_back({cnt, cnt3});
if(cnt<=lim && v3[lim-cnt]!=LLONG_MAX)res=min(res, cnt3+v3[lim-cnt]);
for(auto& [y, w]: adj[n]){
if(y==p || visited[y])continue;
cnt+=w;
cnt3++;
dfs1(y, n);
cnt-=w;
cnt3--;
}
}
ll cnt2=0;
inline void centroid(ll n){
dfs(n, n);
ll o=_find(n, v[n], n);
visited[o]=1;
v2.clear();
ll i=0;
//cout<<o<<endl;
for(auto& [y, w]: adj[o]){
if(visited[y])continue;
cnt3++;
cnt+=w;
dfs1(y, o);
cnt3--;
cnt-=w;
for(; i<v2.size(); i++){v3[v2[i].ft]=min(v3[v2[i].ft], v2[i].sd);if(v2[i].ft==lim)res=min(res, v2[i].sd);}
}
for(auto& [y1, w]: v2)v3[y1]=LLONG_MAX;
for(auto& [y, w]: adj[o]){
if(visited[y])continue;
centroid(y);
}
}
int best_path(int N, int K, int H[][2], int L[]){
ll a, b, c, d, e, f;
a=N;
b=K;
lim=b;
adj.clear();
v.clear();
v3.clear();
visited.clear();
adj.resize(a+1);
v.resize(a+1);
v3.assign(lim+1, LLONG_MAX);
visited.assign(a+1, 0);
for(int i=0; i<a-1; i++){
c=H[i][1];
d=H[i][0];
e=L[i];
adj[c].push_back({d, e});
adj[d].push_back({c, e});
}
centroid(1);
return (res==LLONG_MAX?-1:res);
}
