#include "race.h"
#include <bits/stdc++.h>
#define LL long long
#define ii pair<LL,LL>
#define F first
#define S second
using namespace std;
const int NN=1e3+100;
vector<ii> g[NN];
LL n,k,ans=9e18;
vector<int> vec;
void dfs(int u,int p,LL v,LL dep)
{
// cout<<u<<" "<<p<<endl;
if(v==k){
ans=min(ans,dep);
// for(auto x:vec)cout<<x<<" ";cout<<endl;
}
if(v>k)return;
for(auto x:g[u]){
if(x.F==p)continue;
vec.push_back(x.F);
dfs(x.F,u,v+x.S,dep+1);
vec.pop_back();
}
}
int best_path(int N, int K, int H[][2], int L[])
{
ans=9e18;
n=N;
k=K;
// cout<<endl;
for(int i=0;i<n-1;i++){
int u=H[i][0];
int v=H[i][1];
int w=L[i];
// cout<<u<<" "<<v<<" "<<w<<endl;
g[u].push_back({v,w});
g[v].push_back({u,w});
}
// cout<<endl;
for(int i=0;i<n;i++){
vec.push_back(i);
dfs(i,i,0,0);
vec.pop_back();
}
if(ans==9e18)ans=-1;
int ann=ans;
return ann;
}
/*
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
*/
