#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
template<typename T> bool ckmn(T& a, const T& b){if(a > b) return a = b, true; return false;}
const int _N = 2e5+5, _K = 1e6+5, inf = 1e9;
int n, k, sz[_N];
int MinDist[_K], miniDist;
bool del[_N];
vector<pair<int,int>> adj[_N];
int get_Size(int x, int p){
sz[x] = 1;
for(pair<int,int> e : adj[x]){
int v = e.fi;
if(v != p && !del[v]){
sz[x] += get_Size(v, x);
}
}
return sz[x];
}
int Centroid(int x, int p, int trsz){
for(pair<int,int> e : adj[x]){
int v = e.fi;
if(v != p && !del[v]){
if((sz[v]<<1) > trsz){
return Centroid(v, x, trsz);
}
}
}
return x;
}
queue<int> save;
stack<pair<int,int>> subtr;
void dfs(int x, int p, int cur_dist, int cur_height){
if(MinDist[k - cur_dist] != inf){
ckmn(miniDist, MinDist[k - cur_dist] + cur_height);
}
for(pair<int,int> e : adj[x]){
int v = e.fi, w = e.se;
if(del[v] || v == p) continue;
if(cur_dist <= k - w && cur_height+1 <= miniDist) dfs(v, x, cur_dist+w, cur_height+1);
if(p == -1){
while(!subtr.empty()){
pair<int,int> info = subtr.top(); subtr.pop();
int dist = info.fi, mnH = info.se;
ckmn(MinDist[dist], mnH);
}
}
}
if(p != -1){
save.push(cur_dist);
subtr.push(make_pair(cur_dist, cur_height));
}
else{
while(!save.empty()){
int dist = save.front(); save.pop();
MinDist[dist] = inf;
}
}
return;
}
void decompose(int x){
x = Centroid(x, -1, get_Size(x, -1));
del[x] = true;
dfs(x, -1, 0, 0);
for(pair<int,int> e : adj[x]){
int v = e.fi;
if(!del[v]) decompose(v);
}
return;
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N, k = K;
for(int i = 0; i < n-1; i++){
int u = H[i][0]+1, v = H[i][1]+1, w = L[i];
adj[u].push_back(make_pair(v, w));
adj[v].push_back(make_pair(u, w));
}
miniDist = inf;
for(int i = 1; i <= k; i++){
MinDist[i] = inf;
}
decompose(1);
return (miniDist == inf ? -1 : miniDist);
}
