#include <stdio.h>
#include <vector>
#include <set>
#include <algorithm>
#define pii pair<int,int>
#define ff first
#define ss second
#define INF 1e9
using namespace std;
int n,k;
vector<pii> edge[222222];
int siz[222222];
set<int> st;
vector<pii> vc;
int cnt[1111111];
bool is_cent[222222];
int ans=INF;
int dfs_siz(int v,int p){
siz[v]=1;
for(pii u:edge[v]){
if(u.ff==p || is_cent[u.ff]) continue;
siz[v]+=dfs_siz(u.ff,v);
}
return siz[v];
}
int cent(int rt){
int v=rt,p=rt;
while(1){
int mx=-1,mxi;
for(pii u:edge[v]){
if(u.ff==p || is_cent[u.ff]) continue;
if(mx<siz[u.ff]){
mx=siz[u.ff];
mxi=u.ff;
}
}
if(mx==-1 || mx<=siz[rt]/2) break;
p=v; v=mxi;
}
return v;
}
void dfs_dist(int v,int p,int dist1,int dist2){
vc.push_back({dist1,dist2});
for(pii u:edge[v]){
if(u.ff==p || is_cent[u.ff]) continue;
if(dist1+u.ss<=k) dfs_dist(u.ff,v,dist1+u.ss,dist2+1);
}
}
void cent_dnc(int v){
dfs_siz(v,v);
v=cent(v); is_cent[v]=1;
//printf("%d\n",v);
st.clear();
st.insert(0); cnt[0]=0;
for(pii u:edge[v]){
if(is_cent[u.ff] || u.ss>k) continue;
vc.clear();
dfs_dist(u.ff,v,u.ss,1);
//for(pii dist:vc) printf("%d %d\n",dist.ff,dist.ss);
for(pii dist:vc){
if(st.find(k-dist.ff)!=st.end()) ans=min(ans,cnt[k-dist.ff]+dist.ss);
}
for(pii dist:vc){
if(st.find(dist.ff)==st.end()){
st.insert(dist.ff);
cnt[dist.ff]=dist.ss;
}
else cnt[dist.ff]=min(cnt[dist.ff],dist.ss);
}
//printf("%d\n\n",ans);
}
for(pii u:edge[v]){
if(is_cent[u.ff]) continue;
cent_dnc(u.ff);
}
}
int best_path(int N, int K, int H[][2], int L[]){
n=N; k=K;
for(int i=0;i<n-1;i++){
edge[H[i][0]].push_back({H[i][1],L[i]});
edge[H[i][1]].push_back({H[i][0],L[i]});
}
cent_dnc(0);
if(ans==INF) return -1;
return ans;
}
