#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 1e6;
int current, siz, k, timer = 0, sol = INF;
vector <pair<int, int>> updates;
void get_size(int c, vector <int> g[], bool b[], int s[]){
s[c] = 1; b[c] = 1; siz++;
for (int i = 0; i < g[c].size(); i++){
if (!b[g[c][i]]){
int h = g[c][i]; get_size(h, g, b, s);
s[c] += s[h];
}
}
b[c] = 0;
}
void dfs(int c, vector <int> g[], bool b[], int s[]){
b[c] = 1; int m = 0;
for (int i = 0; i < g[c].size(); i++){
if (!b[g[c][i]]){
int h = g[c][i]; dfs(h, g, b, s);
m = max(m, s[h]);
}
}
b[c] = 0;
if (m <= siz)current = c;
}
void solve(int c, vector <int> g[], vector <int> w[], bool b[], pair<int, int> d[], ll l, int h){
b[c] = 1;
if (l <= k){
if (d[k-l].second < timer){d[k-l].second = timer; d[k-l].first = INF;}
sol = min(sol, d[k-l].first+h);
if (l == k)sol = min(sol, h);
if (d[l].second < timer){d[l].second = timer; d[l].first = INF;}
updates.push_back({l, h});
}
for (int i = 0; i < g[c].size(); i++){
if (!b[g[c][i]])solve(g[c][i], g, w, b, d, l+w[c][i], h+1);
}
b[c] = 0;
}
void centroid_decomposition(int c, vector <int> g[], vector <int> w[], bool b[], int s[], pair<int, int> d[]){
siz = 0; get_size(c, g, b, s); siz /= 2; dfs(c, g, b, s);
int r = current; b[r] = 1;
for (int i = 0; i < g[r].size(); i++){
int v = g[r][i];
if (!b[v]){
solve(v, g, w, b, d, w[r][i], 1);
for (int j = 0; j < updates.size(); j++)d[updates[j].first].first = min(d[updates[j].first].first, updates[j].second);
updates.clear();
}
}
timer++;
for (int i = 0; i < g[r].size(); i++){
if (!b[g[r][i]])centroid_decomposition(g[r][i], g, w, b, s, d);
}
}
int best_path(int N, int K, int H[][2], int L[]){
vector <int> g[N], w[N]; k = K;
pair<int, int> d[k+1]; for (int i = 0; i <= k; i++)d[i] = {INF, 0};
for (int i = 0; i < N-1; i++){
g[H[i][0]].push_back(H[i][1]); g[H[i][1]].push_back(H[i][0]);
w[H[i][0]].push_back(L[i]); w[H[i][1]].push_back(L[i]);
}
bool b[N]; for (int i = 0; i < N; i++)b[i] = 0;
int s[N];
centroid_decomposition(0, g, w, b, s, d);
if (sol == INF)sol = -1;
return sol;
}
/*int main(){
int N, K; cin >> N >> K;
int H[N-1][2], L[N-1]; for (int i = 0; i < N-1; i++)cin >> H[i][0] >> H[i][1] >> L[i];
cerr << best_path(N, K, H, L);
}*/
/*
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
*/
