#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>
#define len(x) (ll)x.size()
const ll inf = 1e9, infl = 1e18;
const ll MOD = 1e9 + 7;
const ll maxn = 1e6 + 5;
ll n, m, k = 0;
const ll lg = 30;
#include "race.h"
ll a[maxn], sz[maxn], vis[maxn];
vector<array<ll, 2>> g[maxn], v;
vll vv;
ll dfs(ll u, ll p = -1){
sz[u] = 1;
for(auto [v, w] : g[u]){
if(v == p or vis[v]) continue;
sz[u] += dfs(v, u);
}
return sz[u];
}
ll fc(ll u, ll p, ll x){
for(auto [v, w] : g[u]){
if(v == p or vis[v]) continue;
if(sz[v] >= sz[x] / 2) return fc(v, u, x);
}
return u;
}
void calc(ll u, ll p, ll lv, ll cm){
v.push_back({cm, lv});
for(auto [v, w] : g[u]){
if(v == p or vis[v]) continue;
calc(v, u, lv + 1, cm + w);
}
}
void centree(ll u){
dfs(u);
ll cent = fc(u, -1, u);
vis[cent] = 1;
a[0] = 0;
for(auto [v, w] : g[cent]){
if(vis[v]) continue;
::v.clear();
calc(v, cent, 1, w);
for(auto [x, y] : ::v){
if(x <= m) k = min(k, y + a[m - x]);
}
for(auto [x, y] : ::v){
if(a[x] > y){
a[x] = y;
vv.push_back(x);
}
}
}
for(auto x : vv) a[x] = infl;
for(auto [v, w] : g[cent]) if(!vis[v]) centree(v);
}
int best_path(int N, int K, int H[][2], int L[]){
n = N, m = K;
for(ll i = 1; i <= n - 1; i ++){
g[H[i - 1][0] + 1].push_back({H[i - 1][1] + 1, L[i - 1]});
g[H[i - 1][1] + 1].push_back({H[i - 1][0] + 1, L[i - 1]});
}
for(ll i = 0; i <= k; i ++) a[i] = infl;
k = infl;
centree(1);
if(k == infl) k = -1;
return k;
}
// void _() {
// }
// signed main() {
// cin.tie(0)->sync_with_stdio(0);
// ll t = 1;
// // cin >> t;
// while(t --) _();
// }
