#include<bits/stdc++.h>
#define ii pair<int,int>
#define fi first
#define se second
#define int long long
#define task ""
using namespace std;
const int N = 2e5 + 10, mod = 1e9 + 7;
const int oo = 1e18;
int n, k, ans, mi[N], ma_h;
int sz[N], h[N], par[N], root;
bool is_centroid[N];
vector<ii> g[N];
void dfs(int u, int par){
sz[u] = 1;
for(ii k : g[u]){
int v = k.fi, c = k.se;
if(v == par || is_centroid[v]) continue;
dfs(v, u);
sz[u] += sz[v];
}
}
int find_centroid(int u, int sz_tree, int par){
for(ii k : g[u]){
int v = k.fi, c = k.se;
if(v != par && !is_centroid[v] && sz[v] > sz_tree/2)
return find_centroid(v, sz_tree, u);
}
return u;
}
void get(int u, int par, int h, int w, int t){
if(w > k) return;
if(t == 0)
ans = min(ans, mi[k - w] + h);
else
mi[w] = min(mi[w], h);
ma_h = max(ma_h, w);
for(ii k : g[u]){
int v = k.fi, c = k.se;
if(v == par || is_centroid[v]) continue;
get(v, u, h + 1, w + c, t);
}
}
void build_centroid(int u, int par){
dfs(u, -1);
int centroid = find_centroid(u, sz[u], -1);
// cout << u << ' ' << sz[u] << '\n';
// cout << u << ' ' << centroid << '\n';
if(root == 0) root = centroid;
is_centroid[centroid] = 1;
for(ii k : g[centroid]){
int v = k.fi, c = k.se;
if(!is_centroid[v]){
get(v, centroid, 1, c, 0);
get(v, centroid, 1, c, 1);
}
}
for(int i = 1; i <= ma_h; i++) mi[i] = oo;
for(ii k : g[centroid]){
int v = k.fi;
if(!is_centroid[v]) build_centroid(v, u);
}
}
int best_path(int N, int K, int H[][2], int w[]){
n = N; k = K;
for(int i = 0; i < n - 1; i++){
H[i][0]++; H[i][1]++;
g[H[i][0]].push_back(ii(H[i][1], w[i]));
g[H[i][1]].push_back(ii(H[i][0], w[i]));
}
// memset(is_centroid, 0, sizeof(is_centroid));
for(int i = 1; i <= k; i++)
mi[i] = oo;
ans = oo;
build_centroid(1, -1);
return (ans == oo ? -1 : ans);
}
// main(){
// 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);
// }
// int N, K;
// int H[200005][2], L[200005];
// cin >> N >> K;
// for(int i = 0; i < N - 1; i++){
// cin >> H[i][0] >> H[i][1] >> L[i];
// }
// cout << best_path(N, K, H, L);
// }
