#include<bits/stdc++.h>
using namespace std;
std::vector<bool>Active;
std::vector<bool>Visited;
vector<vector<pair<int,int>>> Edges;
int n,k;
int opt=1000000000;
int getAm(int parent,int root){
Visited[root]=false;
int am=1;
for(int i=0;i<Edges[root].size();i++){
if(Active[Edges[root][i].first] && Edges[root][i].first!=parent ){
am+=getAm(root,Edges[root][i].first);
}
}
return am;
}
int getCentroid(int parent,int root,int Total,int& centroid){
int am=1;
int maxi=0;
for(int i=0;i<Edges[root].size();i++){
if(Active[Edges[root][i].first] && Edges[root][i].first!=parent){
int k=getCentroid(root,Edges[root][i].first,Total,centroid);
am+=k;
maxi=max(maxi,k);
}
}
if(maxi<=(Total+1)/2 && (Total-am)<=((Total+1)/2)){
centroid=root;
}
return am;
}
void getDfsDists(int parent,int root,int dist,map<int,int>& NewD,int els){
if(NewD[dist]==0){
NewD[dist]=els;
}
NewD[dist]=min(NewD[dist],els);
for(int i=0;i<Edges[root].size();i++){
if(Active[Edges[root][i].first] && Edges[root][i].first!=parent){
getDfsDists(root,Edges[root][i].first,dist+Edges[root][i].second,NewD,els);
}
}
return;
}
void checkPossible(int n){
int centroid;
getCentroid(-1,n,getAm(-1,n),centroid);
map<int,int> Dists;
Dists[0]=1;
for(int i=0;i<Edges[centroid].size();i++){
map<int,int> NewDists;
if(Active[Edges[centroid][i].first]){
getDfsDists(centroid,Edges[centroid][i].first,Edges[centroid][i].second,NewDists,2);
}
for(auto j : NewDists){
int dist=j.first;
int val=j.second;
if(Dists[k-dist]!=0){
opt=min(opt,val+Dists[k-dist]-2);
}
if(Dists[dist]==0){
Dists[dist]=val;
}
Dists[dist]=min(val, Dists[dist]);
}
}
Active[centroid]=false;
}
void getBest(){
for(int j=0;j<80;j++){
Visited=vector<bool>(n,true);
for(int i=0;i<n;i++){
if(Visited[i] && Active[i]){
checkPossible(i);
}
}
}
}
int best_path(int N, int K, int H[][2], int L[]){
n=N;k=K;
Active=vector<bool> (N,true);
Edges=vector<vector<pair<int,int>>>(N);
for(int i=0;i<N-1;i++){
Edges[H[i][0]].push_back({H[i][1],L[i]});
Edges[H[i][1]].push_back({H[i][0],L[i]});
}
getBest();
if(opt!=1000000000){
return opt;
}
return -1;
}
