#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
vector<vector<pair<int,int>>> g;
vector<int> child;
vector<char> rm;
int dfs(int i,int p){
child[i]=1;
for(auto x:g[i]){
int z=x.first;
if(z!=p and rm[z]==0)
child[i]+=dfs(z,i);
}
return child[i];
}
int center(int i,int p,int ts){
int n=ts/2;
for(auto x:g[i]){
int z=x.first;
if(z==p or rm[z]==1){
continue;
}
if(child[z]>n){
return center(z,i,ts);
}
}
return i;
}
map<int,int> mp;
int k,D=1e9;
void dfs1(int i,int p,map<int,int> &mp1,int d,int de){
if(d>k){
return;
}
if(mp1.find(d)==mp1.end()){
mp1[d]=de;
}else{
mp1[d]=min(mp1[d],de);
}
if(mp.find(k-d)!=mp.end()){
D=min(D,mp[k-d]+de);
}
for(auto z:g[i]){
if(p==z.first or rm[z.first]==1){
continue;
}
dfs1(z.first,i,mp1,d+z.second,de+1);
}
}
void build(int i){
dfs(i,-1);
int c=center(i,-1,child[i]);
rm[c]=1;
mp.clear();
for(auto z:g[c]){
if(rm[z.first]==1){
continue;
}
map<int,int> mp1;
dfs1(z.first,c,mp1,z.second,1);
for(auto x:mp1){
if(mp.find(x.first)==mp.end()){
mp[x.first]=x.second;
}else{
mp[x.first]=min(mp[x.first],x.second);
}
}
}
if(mp[k]!=0)
D=min(D,mp[k]);
for(auto z:g[c]){
if(rm[z.first]==0)
build(z.first);
}
}
int best_path(int N,int K,int H[][2],int L[]){
int n;
n=N;
k=K;
D=1e9;
g.clear();
rm.clear();
child.clear();
g.resize(n);
rm.resize(n,0);
child.resize(n);
for(int a=0;a<n-1;a++){
int u=H[a][0],v=H[a][1],x=L[a];
g[u].push_back({v,x});
g[v].push_back({u,x});
}
build(0);
if(D==1e9){
D=-1;
}
return D;
}
//signed main(){
// ios::sync_with_stdio();
// cin.tie(0);
// cout.tie(0);
//// freopen("yinyang.in", "r", stdin);
//// freopen("yinyang.out", "w", stdout);
// ll t=1;
//// cin>>t;
// for(ll a=0;a<t;a++){
// solve();
// }
//}
