#include <bits/stdc++.h>
using namespace std ;
template<class X, class Y>
bool minimize(X &x, const Y &y) {
if(x > y) return x = y, true ;
return false ;
}
const int inf = 1e9 ;
const int lim = 1e6 + 5 ;
struct E {
int u, v, w ;
E() {}
E(int a, int b, int c): u(a), v(b), w(c) {}
};
int g[lim], child[lim], n, k, res = inf ;
vector<int> adj[lim] ;
bitset<lim> del ;
E e[lim] ;
int other(int i, int u) {
return e[i].u ^ e[i].v ^ u ;
}
void dfs(int u, int par) {
child[u] = 1 ;
for(int i : adj[u]) {
int v = other(i, u) ;
if(!del[v] && v != par) {
dfs(v, u) ;
child[u] += child[v] ;
}
}
}
int find_centroid(int u, int par, int cur) {
for(int i : adj[u]) {
int v = other(i, u) ;
if(!del[v] && v != par && child[v] > (cur >> 1)) {
return find_centroid(v, u, cur) ;
}
}
return u ;
}
void dfs_calc(int u, int par, int h, int len) {
if(len > k) return ;
minimize(res, h + g[k - len]) ;
for(int i : adj[u]) {
int v = other(i, u) ;
if(!del[v] && v != par) {
dfs_calc(v, u, h + 1, len + e[i].w) ;
}
}
}
void dfs_up(int u, int par, int h, int len, vector<int> &tmp) {
if(len > k) return ;
tmp.push_back(len) ;
minimize(g[len], h) ;
for(int i : adj[u]) {
int v = other(i, u) ;
if(!del[v] && v != par) {
dfs_up(v, u, h + 1, len + e[i].w, tmp) ;
}
}
}
void decomp(int root) {
// cerr << root << ' ' ;
dfs(root, 0) ;
root = find_centroid(root, 0, child[root]) ;
vector<int> tmp ;
for(int i : adj[root]) {
int v = other(i, root) ;
if(!del[v]) {
dfs_calc(v, root, 1, e[i].w) ;
dfs_up(v, root, 1, e[i].w, tmp) ;
}
}
del.set(root) ;
for(int k : tmp) {
g[k] = inf ;
}
for(int i : adj[root]) {
int v = other(i, root) ;
if(!del[v]) {
decomp(v) ;
}
}
}
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 ;
e[i] = E(u, v, L[i]) ;
adj[u].push_back(i) ;
adj[v].push_back(i) ;
}
for(int i = 1; i <= lim; i ++) {
g[i] = inf ;
}
decomp(1) ;
return res == inf ? -1 : res ;
}
