#include<bits/stdc++.h>
using namespace std;
#define range(v) begin(v), end(v)
#define compact(v) v.erase(unique(range(v)), end(v))
template<class T> bool minimize(T& a, T b){
if(a > b) return a = b, true;
return false;
}
template<class T> bool maximize(T& a, T b){
if(a < b) return a = b, true;
return false;
}
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int N = 1e5 + 5;
const int inf = 1e9;
int n, k, ans = inf, sz[N];
bool del[N];
vector<pair<int, int>> g[N];
int dfsSize(int u, int e){
sz[u] = 1;
for(auto [v, w] : g[u]) if(v != e and !del[v]){
sz[u] += dfsSize(v, u);
}
return sz[u];
}
int getCentroid(int u, int e, int target){
for(auto [v, w] : g[u]) if(v != e and !del[v] and sz[v] * 2 > target){
return getCentroid(v, u, target);
}
return u;
}
map<int, int> cnt;
stack<pair<int, int>> op;
void init(){
cnt.clear();
}
void add(int w, int l){
if(cnt.find(w) == cnt.end()) cnt[w] = l;
else minimize(cnt[w], l);
}
int query(int target){
if(target == 0) return 0;
if(cnt.find(target) == cnt.end()) return inf;
return cnt[target];
}
void dfs(int u, int e, int sumW, int sumL){
if(sumW > k) return;
op.push({sumW, sumL});
minimize(ans, query(k - sumW) + sumL);
for(auto [v, w] : g[u]) if(v != e and !del[v]){
dfs(v, u, sumW + w, sumL + 1);
}
}
void decompose(int u, int e){
int c = getCentroid(u, e, dfsSize(u, e));
del[c] = true;
init();
for(auto [v, w] : g[c]) if(!del[v]){
dfs(v, c, w, 1);
while(!op.empty()){
add(op.top().first, op.top().second);
op.pop();
}
}
for(auto [v, w] : g[c]) if(!del[v]){
decompose(v, c);
}
}
int best_path(int N, int K, int H[][2], int L[]){
n = N, k = K;
for(int i = 0; i + 1 < n; ++i){
int u = H[i][0], v = H[i][1], w = L[i];
g[u].push_back({v, w});
g[v].push_back({u, w});
}
decompose(0, 0);
return (ans == inf ? -1 : ans);
}
//void Zero_OP(){
// cin >> n >> k;
// for(int i = 1; i < n; ++i){
// int u, v, w;
// cin >> u >> v >> w;
// g[u].push_back({v, w});
// g[v].push_back({u, w});
// }
//
// decompose(0, 0);
// cout << (ans == inf ? -1 : ans) << '\n';
//}
//
//int main(){
// ios_base::sync_with_stdio(0);
// cin.tie(0);
//
// #define task "antuvu"
// if(fopen(task".inp", "r")){
// freopen(task".inp", "r", stdin);
// freopen(task".out", "w", stdout);
// }
//
// Zero_OP();
//
// return 0;
//}
