#include<bits/stdc++.h>
#include "race.h"
using namespace std;
#define int long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(), (a).end()
#define task "kbsiudthw"
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<int, ii> pii;
const int N = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 2277;
int ans = 1e18, sz[N], block[N], best[N], k;
vector<ii> G[N];
int get_subtree_size(int u, int par = 0){
sz[u] = 1;
for (ii &v : G[u]){
if (block[v.fi] || v.fi == par) continue;
sz[u] += get_subtree_size(v.fi, u);
}
return sz[u];
}
int get_centroid(int u, int sub_sz, int par = 0){
for (ii &v : G[u]){
if (v.fi == par || block[v.fi]) continue;
if (sz[v.fi] * 2 > sub_sz) return get_centroid(v.fi, sub_sz, u);
}
return u;
}
vector<ii> all, sub;
void dfs(int u, int h, int dist, int par = 0){
if (dist > k) return;
sub.pb({dist, h});
all.pb({dist, h});
ans = min(ans, h + best[k - dist]);
for (ii & v: G[u]){
if (v.fi == par || block[v.fi]) continue;
dfs(v.fi, h + 1, dist + v.se, u);
}
}
void Centroid(int u){
int centroid = get_centroid(u, get_subtree_size(u));
block[centroid] = 1;
best[0] = 0;
for (ii & v: G[centroid]){
dfs(v.fi, 1, v.se, u);
for (ii &x : sub){
best[x.fi] = min(best[x.fi], x.se);
}
sub.clear();
}
for (ii &x : all) best[x.fi] = 1e18;
all.clear();
for (ii &x : G[centroid]){
Centroid(x.fi);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
FOR (i, 1, N) best[i] = 1e18;
k = K;
FOR (i, 0, N - 2){
int u = H[i][0] + 1, v = H[i][1] + 1, w = L[i];
G[u].pb({v, i});
G[v].pb({u, i});
}
Centroid(1);
return (ans == 1e18 ? -1 : ans);
}
