#include "race.h"
#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7, MAXK=1e6+7;
vector<pair<int,int>>V[LIM];
int usuniete[LIM], ile[LIM], rozmiar, ans, n, k, nr;
pair<int,int>T[MAXK];
queue<int>q;
void DFS(int x, int o) {
q.push(x);
++rozmiar;
ile[x]=1;
for(auto i : V[x]) if(i.st!=o && !usuniete[i.st]) {
DFS(i.st, x);
ile[x]+=ile[i.st];
}
}
int znajdz(int x) {
rozmiar=0;
DFS(x, x);
int ma=LIM, cent=-1;
while(!q.empty()) {
int p=q.front(), akt=rozmiar-ile[p]; q.pop();
for(auto i : V[p]) if(!usuniete[i.st]) {
if(ile[i.st]<ile[p]) akt=max(akt, ile[i.st]);
}
if(akt<ma) {
ma=akt;
cent=p;
}
}
return cent;
}
void licz(int x, int o, int v, int g) {
if(v>k) v=k+1;
if(v<=k && T[k-v].nd==nr) {
ans=min(ans, T[k-v].st+g);
}
for(auto i : V[x]) if(i.st!=o && !usuniete[i.st]) licz(i.st, x, v+i.nd, g+1);
}
void ustaw(int x, int o, int v, int g) {
if(v>k) v=k+1;
if(v<=k) {
if(T[v].nd<nr || T[v].st>g) T[v]={g, nr};
}
for(auto i : V[x]) if(i.st!=o && !usuniete[i.st]) ustaw(i.st, x, v+i.nd, g+1);
}
void cd(int x) {
int p=znajdz(x);
usuniete[p]=1;
++nr;
T[0]={0, nr};
for(auto i : V[p]) if(!usuniete[i.st]) {
licz(i.st, p, i.nd, 1);
ustaw(i.st, p, i.nd, 1);
}
for(auto i : V[p]) if(!usuniete[i.st]) cd(i.st);
}
int best_path(int N, int K, int h[][2], int l[]) {
n=N; k=K;
rep(i, n-1) {
V[h[i][0]].pb({h[i][1], l[i]});
V[h[i][1]].pb({h[i][0], l[i]});
}
ans=LIM;
cd(0);
if(ans==LIM) return -1;
return ans;
}
