#include <bits/stdc++.h>
#include "race.h"
#define X first
#define Y second
#define pb push_back
#define pii pair<int, int>
typedef long long ll;
using namespace std;
const int MOD = 1e9 + 7;
const ll INF = 1e18;
const int OFF = (1 << 20);
int n, k, sol = 1e9;
vector< pair<int, int> > v[200005];
int kol[200005];
ll d[200005];
int bio[200005];
int w[1000005];
void dfs(int x, int p, ll dist) {
d[x] = dist;
kol[x]++;
for (int i = 0; i < v[x].size(); i++) {
if (v[x][i].X != p) {
dfs(v[x][i].X, x, dist+v[x][i].Y);
kol[x] += kol[v[x][i].X];
}
}
}
void postavi(int x, int p, ll l1, int l2) {
if (l1 <= k) w[l1] = min(w[l1], l2);
for (int i = 0; i < v[x].size(); i++) {
if (v[x][i].X != p && bio[v[x][i].X] == 0) postavi(v[x][i].X, x, l1+v[x][i].Y, l2+1);
}
}
void odstavi(int x, int p, ll l1, int l2) {
if (l1 <= k) w[l1] = 1e9;
for (int i = 0; i < v[x].size(); i++) {
if (v[x][i].X != p && bio[v[x][i].X] == 0) odstavi(v[x][i].X, x, l1+v[x][i].Y, l2+1);
}
}
void racunaj(int x, int p, ll l1, int l2) {
if (l1 <= k && w[k-l1] != 1e9) sol = min(sol, w[k-l1]+l2);
for (int i = 0; i < v[x].size(); i++) {
if (v[x][i].X != p && bio[v[x][i].X] == 0) racunaj(v[x][i].X, x, l1+v[x][i].Y, l2+1);
}
}
void centroidna(int x, int siz) {
while (1) {
int maxi = -1, gdje = -1;
for (int i = 0; i < v[x].size(); i++) {
if (bio[v[x][i].X] == 0 && kol[v[x][i].X] > maxi) {
maxi = kol[v[x][i].X];
gdje = v[x][i].X;
}
}
if (maxi > siz/2) {
int pri = kol[gdje];
kol[gdje] = kol[x];
kol[x] -= pri;
x = gdje;
}
else break;
}
bio[x] = 1;
w[0] = 0;
for (int i = 0; i < v[x].size(); i++) {
if (bio[v[x][i].X] == 0) {
racunaj(v[x][i].X, x, v[x][i].Y, 1);
postavi(v[x][i].X, x, v[x][i].Y, 1);
}
}
for (int i = 0; i < v[x].size(); i++) {
if (bio[v[x][i].X] == 0) odstavi(v[x][i].X, x, v[x][i].Y, 1);
}
w[0] = 1e9;
for (int i = 0; i < v[x].size(); i++) {
if (bio[v[x][i].X] == 0) centroidna(v[x][i].X, kol[v[x][i].X]);
}
}
int best_path(int N, int K, int h[][2], int l[]) {
n = N;
k = K;
for (int i = 0; i < n-1; i++) {
v[h[i][0]].push_back({h[i][1], l[i]});
v[h[i][1]].push_back({h[i][0], l[i]});
}
for (int i = 0; i <= k; i++) w[i] = 1e9;
dfs(0, -1, 0);
centroidna(0, n);
if (sol == 1e9) return -1;
else return sol;
}
