#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int M=2e5+55;
vector < pair < int , int > > vec[M];
int k[M][105];
int b=1e9+55;
void dfs(int u , int p , int K)
{
int v,c;
int temp;
for(auto x:vec[u])
{
v=x.first;
c=x.second;
if(v==p)
continue ;
dfs(v,u,K);
for(int i=0;i<=K-c;i++)
b=min(b,k[v][i]+k[u][K-i-c]+1);
for(int i=0;i<=K-c;i++)
{
temp=k[v][i];
k[u][i+c]=min(k[u][i+c],temp+1);
}
}
b=min(b,k[u][K]);
}
void df(int u , int p , int cnt , int c , int k)
{
if(cnt==k)
{
b=min(b,c);
return ;
}
if(cnt>k)
return ;
int v,x;
for(auto a:vec[u])
{
v=a.first;
x=a.second;
if(v==p)
continue ;
df(v,u,cnt+x,c+1,k);
}
}
int best_path(int n, int K, int H[][2], int L[])
{
for(int i=0;i<n-1;i++)
{
vec[H[i][0]].push_back({H[i][1],L[i]});
vec[H[i][1]].push_back({H[i][0],L[i]});
}
if(K>100)
{
b=1e9+55;
for(int i=0;i<n;i++)
{
df(i,-1,0,0,K);
}
if(b==1e9+55)
return -1;
return b;
}
for(int i=0;i<n;i++)
{
for(int j=1;j<=K;j++)
k[i][j]=1e9+55;
}
dfs(0,-1,K);
return (b==1e9+55?-1:b);
}
