#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long 

vector<vector<array<int , 2>>> adj; 
int dp[(int)2e5+1][101][3];
int k ; 

void dfs1(int node  ,  int par){
  for (auto &[i , w] : adj[node]){
    if (i == par) continue;    
    dfs1(i , node); 
    for (int j = 0 ; j <= k ; j++){
      if (j >= w) {
          if (dp[i][j-w][0] + 1 <= dp[node][j][0]) {
            dp[node][j][1] = dp[node][j][0];
            dp[node][j][0] = dp[i][j-w][0] + 1; 
          } 
          else if (dp[i][j-w][0] + 1 <= dp[node][j][1]){
            dp[node][j][1] = dp[i][j-w][0] + 1; 
          }
      }
    }
  }
}

void dfs2(int node , int par){
  for (auto &[i , w] : adj[node]){
    if (i == par) continue;
    for (int j = 0 ; j <= k ; j++){
      dp[i][j][2] = min(dp[i][j][2] , dp[i][j][0]); 
      if (j >= w) {
        int odp = (j >= 2*w && dp[node][j-w][2] == dp[i][j-2*w][0] + 1 ? dp[node][j-w][1] : dp[node][j-w][2]); 
        dp[i][j][2] = min(dp[i][j][2] , odp + 1); 
      }
    }
    dfs2(i , node); 
  }
}



signed best_path(signed N, signed K, signed H[][2], signed L[])
{
  adj.assign(N , {}); 
  k = K; 
  for (int i = 0 ; i < N-1 ; i++){
    adj[H[i][0]].push_back({H[i][1] , L[i]});
    adj[H[i][1]].push_back({H[i][0] , L[i]}); 
  }
  for (int i = 0 ; i <= N ; i++){
    for (int j = 1  ; j <= K; j++) {
      for (int l = 0 ; l < 3 ; l++){
        dp[i][j][l] = 1e9; 
      }
    }
  }
  dfs1(0 , -1);
  for (int j = 0 ; j <= K; j++) dp[0][j][2] = dp[0][j][0]; 
  dfs2(0 , -1); 
  int ans = 1e9; 
  for (int i = 0 ; i < N ; i++){
    ans = min(ans , dp[i][k][2]); 
  }
  return (ans == 1e9 ? -1 : ans);
}