//#include "race.h"
#include<bits/stdc++.h>
using namespace std;
///Subtask 3
///DFS with buckets
typedef long long ll;
struct edge
{
int to;
ll w;
};
vector<edge> adjList[200005];
int k;
int minimum=INT_MAX;
void dfs_sub2(int u,int p,int depth,ll path)
{
if(path==k) minimum=min(minimum,depth);
for(edge e: adjList[u]){
int v=e.to;
ll w=e.w;
if(p==v) continue;
dfs_sub2(v,u,depth+1,path+w);
}
}
ll parent_way[200005];
void fillParent(int u,int p)
{
for(edge e: adjList[u]){
int v=e.to;
ll w=e.w;
if(v==p) continue;
parent_way[v]=w;
fillParent(v,u);
}
}
vector<int>* bucket[200005];
void dfs(int u,int p)
{
int leaf=1;
for(edge e: adjList[u]){
int v=e.to;
ll w=e.w;
if(p==v) continue;
leaf=0;
dfs(v,u);
}
bucket[u]=new vector<int>(101);
for(edge e: adjList[u]){
int v=e.to;
ll w=e.w;
if(p==v) continue;
for(int i=0;i<k;i++){
int path_child=(*bucket[v])[i];
int path=(*bucket[u])[k-i];
if(path_child==0) continue;
if(path!=0)
minimum=min(minimum,path_child+path);
if((*bucket[u])[i]==0)
(*bucket[u])[i]=path_child;
else
(*bucket[u])[i]=min((*bucket[u])[i],path_child);
}
if((*bucket[v])[k]!=0) minimum=min(minimum,(*bucket[v])[k]);
}
if(leaf) (*bucket[u])[ parent_way[u] ]=1;
if((*bucket[u])[k]!=0)
minimum=min(minimum,(*bucket[u])[k]);
if(!leaf){
for(int i=k;i>=1;i--){
if((ll)i+parent_way[u]>k) continue;
int dist=i+parent_way[u];
if((*bucket[u])[i]!=0){
(*bucket[u])[dist]=(*bucket[u])[i]+1;
if(dist!=i) (*bucket[u])[i]=0;
}
}
(*bucket[u])[ parent_way[u] ]=1;
}
}
int best_path(int n, int K, int H[][2], int L[])
{
k=K;
for(int i=0;i<n-1;i++){
int a=H[i][0];
int b=H[i][1];
ll w=L[i];
adjList[a].push_back({b,w});
adjList[b].push_back({a,w});
}
if(n<=1000){
for(int u=0;u<n;u++){
dfs_sub2(u,-1,0,0);
}
return (minimum!=INT_MAX)? minimum : -1;
}
fillParent(0,-1);
dfs(0,-1);
/*for(int i=0;i<n;i++){
cout<<i<<":";
for(int j=0;j<=k;j++){
if((*bucket[i])[j]!=0) cout<<j<<" "<<(*bucket[i])[j]<<endl;
}
cout<<endl;
}*/
return (minimum!=INT_MAX)? minimum : -1;
}
