#include <bits/stdc++.h>
#include "race.h"
using namespace std;
const int N = 1e6 + 5;
int n, cnt, k;
int dd[N], sz[N], d[N], f[N];
vector <pair<int, int>> ad[N], val;
int ans;
void dfs(int u, int par) {
cnt++;
sz[u] = 1;
for(auto v : ad[u]) {
if(v.first != par && !dd[v.first]) dfs(v.first, u), sz[u] += sz[v.first];
}
}
int ftr(int u, int par) {
for(auto &v : ad[u]) if(v.first != par && !dd[v.first] && sz[v.first] > cnt / 2) return ftr(v.first, u);
return u;
}
void bfs(int u, int par, int len, int cnt) {
if(len > k) return;
val.emplace_back(len, cnt);
for(auto &v : ad[u]) {
if(v.first != par && !dd[v.first] && v.second + len <= k) {
bfs(v.first, u, v.second + len, cnt + 1);
}
}
}
void ctr(int u, int par) {
cnt = 0;
dfs(u, 0);
int c = ftr(u, u);
dd[c] = 1;
f[0] = 0;
vector<int> del;
for(auto v : ad[c]) {
if(!dd[v.first]) {
bfs(v.first, c, v.second, 1);
for(auto &i : val) if(k >= i.first && f[k - i.first] != -1) ans = min(ans, i.second + f[k - i.first]);
for(auto &i : val) f[i.first] = (f[i.first] < 0) ? i.second : min(i.second, f[i.first]), del.emplace_back(i.first);
val.clear();
}
}
for(auto &v : del) f[v] = -1;
for(auto &v : ad[c]) if(!dd[v.first]) ctr(v.first, c);
}
int best_path(int _n, int _k, int h[][2], int l[]) {
n = _n, k = _k;
for(int i = 0; i < n - 1; ++i) {
int u = h[i][0], v = h[i][1], c = l[i]; u++; v++;
ad[u].emplace_back(v, c);
ad[v].emplace_back(u, c);
}
memset(f, -1, sizeof(f));
ans = INT_MAX;
ctr(1, 0);
return (ans == INT_MAX) ? -1 : ans;
}
/*
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> k;
static int h[N][2], le[N];
for(int i = 0; i < n - 1; ++i) cin >> h[i][0] >> h[i][1] >> le[i];
cout << best_path(n, k, h, le);
}
*/
