#pragma GCC optimize("Ofast")
#include "race.h"
#include<bits//stdc++.h>
using namespace std;
const int n=2e5;
int k,ans=n+5;
vector<vector<pair<int,int>>>graph;
map<int,int>dp[n];
void dfs(int u,int p,int le){
dp[u][0]=0;
int v,l;
for(auto&i:graph[u])if(i.first!=p){
dfs(v=i.first,u,l=i.second);
if(dp[u].size()<dp[v].size())dp[u].swap(dp[v]);
for(auto&j:dp[v]){
if(dp[u].find(k-j.first)!=end(dp[u]))ans=min(ans,dp[u][k-j.first]+j.second);
}
for(auto&j:dp[v]){
if(ans<=j.second+1)continue;
if(dp[u].find(j.first)==end(dp[u]))dp[u][j.first]=j.second;
else dp[u][j.first]=min(dp[u][j.first],j.second);
}
}
map<int,int>cur;
for(auto&i:dp[u]){
if(i.first==k)ans=min(ans,i.second);
if(i.first+le>k)break;
cur[i.first+le]=i.second+1;
}
dp[u]=cur;
}
int best_path(int N, int K, int H[][2], int L[])
{
graph.resize(N);
for(int i=0;i<N-1;++i){
graph[H[i][0]].push_back({H[i][1],L[i]});
graph[H[i][1]].push_back({H[i][0],L[i]});
}
k=K;
dfs(0,0,0);
return (ans==n+5?-1:ans);
}
