#include "race.h"
#include <vector>
#include <map>
#include <stdint.h>
static const int INF=1e9+7;
static std::vector<std::pair<int,int> > adj[200005];
static int ans=INF;
static int size[200005];
static int KK;
static bool dead[200005];
static int best[1000005];
static int dfs_size(int node,int parent){
size[node]=1;
for(auto e:adj[node]){
int child=e.first;
if(dead[child]||child==parent) continue;
dfs_size(child,node);
size[node]+=size[child];
}
}
static int find_centroid(int node,int parent,int total_size){
for(auto e:adj[node]){
int child=e.first;
if(dead[child]||child==parent) continue;
if(size[child]*2>total_size){
return find_centroid(child,node,total_size);
}
}
return node;
}
static void dfs_add(int node,int parent,int64_t dist,int len){
if(dist>KK) return;
best[dist]=std::min(best[dist],len);
for(auto e:adj[node]){
int child=e.first;
if(dead[child]||child==parent) continue;
dfs_add(child,node,dist+e.second,len+1);
}
}
static void dfs_test(int node,int parent,int64_t dist,int len){
if(dist>KK) return;
ans=std::min(ans,best[KK-dist]+len);
for(auto e:adj[node]){
int child=e.first;
if(dead[child]||child==parent) continue;
dfs_test(child,node,dist+e.second,len+1);
}
}
static void dfs_rem(int node,int parent,int64_t dist,int len){
if(dist>KK) return;
best[dist]=INF;
for(auto e:adj[node]){
int child=e.first;
if(dead[child]||child==parent) continue;
dfs_rem(child,node,dist+e.second,len+1);
}
}
static void solve(int node){
dfs_size(node,node);
node=find_centroid(node,node,size[node]);
best[0]=0;
for(auto e:adj[node]){
int child=e.first;
if(dead[child]) continue;
dfs_test(child,node,e.second,1);
dfs_add(child,node,e.second,1);
}
for(auto e:adj[node]){
int child=e.first;
if(dead[child]) continue;
dfs_rem(child,node,e.second,1);
}
dead[node]=true;
for(auto e:adj[node]){
int child=e.first;
if(dead[child]) continue;
solve(child);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
for(int i=0;i<N;i++){
adj[i].clear();
}
ans=INF;
std::fill(dead,dead+N,false);
KK=K;
std::fill(best,best+1000001,INF);
for(int i=0;i<N-1;i++){
adj[H[i][0]].emplace_back(H[i][1],L[i]);
adj[H[i][1]].emplace_back(H[i][0],L[i]);
}
solve(0);
return ans<INF?ans:-1;
}
