/* 29 . 03. 2008 */
# include <bits/stdc++.h>
using namespace std ;
const int N = 2e5 + 5 ;
const int M = 1e6 + 5 ;
const long long inf = 1e18 ;
int n, k ;
vector <pair<int,int>> g[N] ;
int is_centroid[N], sz[N] ;
int cnt[M] ;
int ans ;
void dfs(int u, int p) {
sz[u] = 1 ;
for(pair<int, int> x : g[u]) {
int v = x.first ;
if(v == p || is_centroid[v]) continue ;
dfs(v, u) ;
sz[u]+= sz[v] ;
}
}
int findCentroid(int u, int p, int big) {
for(pair<int, int> x : g[u]) {
int v = x.first ;
if(v == p || is_centroid[v]) continue ;
if(sz[v] > big / 2) return findCentroid(v, u, big) ;
}
return u ;
}
int max_depth ;
void updateAns(int u, int p, int t, int d, int w) {
if(w > k) return ;
if(t == 1) cnt[w] = min(cnt[w], d) ;
else ans = min(ans, cnt[k - w] + d) ;
max_depth = max(max_depth, w) ;
for(pair<int, int> x : g[u]) {
int v = x.first , len = x.second ;
if(v == p || is_centroid[v]) continue ;
updateAns(v, u, t, d + 1, w + len) ;
}
}
void buildCentroid(int u) {
dfs(u, - 1) ;
int centroid = findCentroid(u, - 1, sz[u]) ;
is_centroid[centroid] = 1 ;
max_depth = 0 ;
for(pair<int, int> x : g[centroid]) {
int v = x.first , w = x.second ;
if(is_centroid[v]) continue ;
updateAns(v, centroid, 0, 1, w) ;
updateAns(v, centroid, 1, 1, w) ;
}
for(int i = 1; i <= max_depth; i++) cnt[i] = 2e9 ;
for(pair<int, int> x : g[centroid]) {
int v = x.first ;
if(!is_centroid[v]) buildCentroid(v) ;
}
}
void solve() {
for(int i = 0; i <= k; i++) cnt[i] = 2e9 ;
ans = 2e9 ;
cnt[0] = 0 ;
buildCentroid(1) ;
cout << (ans >= 2e9 ? - 1 : ans) ;
}
array <int, 2> E[N];
int best_path(int _n, int _k, int h[][2], int l[]){
n = _n;
k = _k;
for(int i = 0; i < n; i++){
h[i][0]++; h[i][1]++;
g[h[i][0]].emplace_back(h[i][1], l[i]);
g[h[i][1]].emplace_back(h[i][0], l[i]);
}
for(int i = 0; i <= k; i++) cnt[i] = 2e9;
ans = 2e9 ;
cnt[0] = 0 ;
buildCentroid(1) ;
return (ans >= 2e9 ? - 1 : ans);
}
// signed main() {
// #define task "race"
// ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ;
// // if(fopen(task".inp", "r")) {
// // freopen(task".inp","r",stdin) ; freopen(task".out","w",stdout) ;
// // }
// // if(fopen(".inp","r")) {
// // freopen(".inp","r",stdin) ; freopen(".out","w",stdout) ;
// // }
// cin >> n >> k ;
// for(int i = 1; i < n; i++) {
// int u, v, w ; cin >> u >> v;
// u++, v++ ;
// E[i] = {u, v};
// // g[u].emplace_back(make_pair(v, w)) ; g[v].emplace_back(make_pair(u, w)) ;
// }
// for(int i = 1; i < n; i++){
// int w; cin >> w;
// int u = E[i][0], v = E[i][1];
// g[u].emplace_back(make_pair(v, w)) ; g[v].emplace_back(make_pair(u, w)) ;
// }
// solve() ;
// cerr << "\nTime :" << 0.001 * clock() << "s " ;
// return 0 ;
// }
/* Watbor */
