#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define A first
#define B second
#define pii pair<int , int>
#define pb push_back

vector<vector<pii>> adj;
int n , k;
int dfs(int node , int par , int dep){
    if (dep == k) return 0;
    int ans = 1e18;
    for (auto i : adj[node]){
        if (i.A!=par){
            ans = min(ans , dfs(i.A , node , dep + i.B)+1);
        }
    }
    return ans;
}

int best_path(int N, int K, int H[][2], int L[])
{
   n = N; k = K;
    adj.resize(n+1);
    for (int i = 0 ; i<n-1 ; i++){
        adj[H[i][0]].pb({H[i][1] , L[i]});
        adj[H[i][1]].pb({H[i][0] , L[i]});
    }
    int ans = 1e18;
    for (int i = 1 ; i<=n ; i++){
        ans = min(ans , dfs(i , -1 , 0));
    }
    if (ans == 1e18) return -1;
    else return ans;
}