#include <bits/stdc++.h>
#define ll long long
#define pii pair < int, int >
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
const int N = 2e5+10, K = 1e6+10, inf = 1e9+10;
int n, k;
vector < pii > adj[N];
bool turnedoff[N];
int distfound[K];
int siz[N];
void dfs( int x, int par ) {
int sus;
siz[x] = 1;
for(int i = 0; i < (int) adj[x].size(); i++) {
sus = adj[x][i].F;
if(sus != par && !turnedoff[sus]) {
dfs(sus, x);
siz[x] += siz[sus];
}
}
return;
}
int find_centroid( int x, int par, int reqsiz ) {
int sus;
pii maxi = mp(0, -1);
for(int i = 0; i < (int) adj[x].size(); i++) {
sus = adj[x][i].F;
if(sus != par && !turnedoff[sus]) {
maxi = max(maxi, mp(siz[sus], sus));
}
}
if(maxi.F <= reqsiz) return x;
return find_centroid(maxi.S, x, reqsiz);
}
int query_dfs( int x, int par, bool doset, bool v, int curv, int curdep ) {
// cout << x << " " << curv << " " << curdep << "\n";
int sus;
if(curv > k) return inf;
if(doset) {
if(!v) distfound[curv] = inf;
else distfound[curv] = min(distfound[curv], curdep);
}
int out = inf;
out = min(out, distfound[k - curv] + curdep);
for(int i = 0; i < (int) adj[x].size(); i++) {
sus = adj[x][i].F;
if(sus != par && !turnedoff[sus]) {
out = min(query_dfs(sus, x, doset, v, curv + adj[x][i].S, curdep + 1), out);
}
}
return out;
}
int cd( int root ) {
dfs(root, root);
int centr = find_centroid(root, root, siz[root] / 2);
turnedoff[centr] = 1;
int out = inf;
int sus;
for(int i = 0; i < (int) adj[centr].size(); i++) {
sus = adj[centr][i].F;
if(!turnedoff[sus]) {
out = min(out, query_dfs(sus, sus, 0, 0, adj[centr][i].S, 1));
query_dfs(sus, sus, 1, 1, adj[centr][i].S, 1);
}
}
// cout << centr << ":\n";
// for(int i = 0; i <= k; i++) cout << distfound[i] << " ";
// cout << "\n\n";
// cout << out << "\n\n";
// query_dfs(centr, centr, 1, 0, 0, 0);
out = min(out, distfound[k]);
query_dfs(centr, centr, 1, 0, 0, 0);
for(int i = 0; i < (int) adj[centr].size(); i++) {
sus = adj[centr][i].F;
if(!turnedoff[sus]) {
out = min(out, cd(sus));
}
}
// cout << out << "\n";
return out;
}
int task( void ) {
// cin >> n >> k;
// for(int i = 0; i < n; i++) adj[i].clear();
// for(int i = 0; i < n; i++) turnedoff[i] = 0;
for(int i = 0; i <= k; i++) distfound[i] = inf;
/* int a, b, c;
for(int i = 0; i < n - 1; i++) {
cin >> a >> b >> c;
adj[a].pb(mp(b, c));
adj[b].pb(mp(a, c));
}*/
int sol = cd(0);
// cout << sol << "\n";
if(sol != inf) return sol;
else return -1;
}
int best_path( int nn, int kk, int hh[][2], int l[] ) {
for(int i = 0; i < nn - 1; i++) {
adj[hh[i][0]].pb(mp(hh[i][1], l[i]));
adj[hh[i][1]].pb(mp(hh[i][0], l[i]));
}
n = nn;
k = kk;
return task();
}
