#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define sp << ' ' <<
#define nl << '\n'
#define v e.first
#define w e.second
#include "race.h"
const int MAXN = 2e5;
int ans = 1e9, k;
vector<vector<pair<int, int>>> g(MAXN);
vector<int> s(MAXN);
vector<bool> r(MAXN);
vector<map<int, int>> d(MAXN);
int calcSize(int u, int p){
s[u] = 0;
for(auto &e : g[u]) if(v != p and !r[v]) s[u] += calcSize(v, u);
return s[u];
}
void calcDist(int u, int p, int currLength, int currDist, int root){
int &x = d[root][currDist];
if(!x) x = currLength+1;
else x = min(x, currLength+1);
for(auto &e : g[u]) if(v != p and !r[v]) calcDist(v, u, currLength, currDist+w, root);
}
void dfs(int u, int p, int currLength, int currDist, int root){
if(d[root][k-currDist]) ans = min(ans, d[root][k-currDist] + currLength);
for(auto &e : g[u]) if(v != p and !r[v]) dfs(v, u, currLength+1, currDist+w, root);
}
int find(int u, int p, int treeSize){
for(auto &e : g[u]) if(v != p and !r[v] and s[v] > treeSize/2) return find(v, u, treeSize);
return u;
}
void decompose(int u){
int c = find(u, u, calcSize(u, u));
r[u] = 1;
for(auto &e : g[c]){
if(r[v]) continue;
dfs(v, c, 1, w, c);
calcDist(v, c, 1, w, c);
}
if(d[c][k]) ans = min(ans, d[c][k]);
for(auto &e : g[c]) if(!r[v]) decompose(v);
}
int best_path(int N, int K, int H[][2], int L[]){
k = K;
for(int i=0; i<N-1; ++i){
g[H[i][0]].emplace_back(H[i][1], L[i]);
g[H[i][1]].emplace_back(H[i][0], L[i]);
}
decompose(0);
if(ans>N) ans = -1;
return ans;
}
