#include <bits/stdc++.h>
using namespace std;
template<class A, class B> bool maximize(A& x, B y) {if (x < y) return x = y, true; else return false;}
template<class A, class B> bool minimize(A& x, B y) {if (x > y) return x = y, true; else return false;}
#define all(a) a.begin(), a.end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
//#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
typedef pair<db, db> pdb;
typedef pair<ld, ld> pld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> plli;
typedef pair<int, ll> pill;
const int MAX_N = 2e5 + 5;
const int mod = 1e9 + 7; // 998244353
const int inf = 1e9 + 1;
int n, k;
vector<pii> adj[MAX_N];
bool processed[MAX_N];
int ans = inf;
int child[MAX_N];
int dfs(int u, int pr = 0) {
child[u] = 1;
for (auto it : adj[u]) {
int v = it.fi;
if (!processed[v] && v != pr) {
child[u] += dfs(v, u);
}
}
return child[u];
}
int find_centroid(int u, int pr, int sz) {
for (auto it : adj[u]) {
int v = it.fi;
if (!processed[v] && v != pr && child[v] > sz) {
return find_centroid(v, u, sz);
}
}
return u;
}
const int MAX_VAL = 1e6 + 10;
int dp[MAX_VAL];
vector<int> used;
void go_cal(int u, int pr, bool ok, int len, int dep) {
if (k < len) return;
if (ok) {
used.pb(len);
minimize(dp[len], dep);
}
else {
minimize(ans, dp[k - len] + dep);
}
for (auto it : adj[u]) {
int v = it.fi;
int w = it.se;
if (!processed[v] && v != pr) {
go_cal(v, u, ok, len + w, dep + 1);
}
}
}
void centroid_decomposition(int u) {
int c = find_centroid(u, 0, dfs(u) >> 1);
processed[c] = true;
used.clear();
dp[0] = 0;
for (auto it : adj[c]) {
int v = it.fi;
int w = it.se;
if (!processed[v]) {
go_cal(v, c, false, w, 1);
go_cal(v, c, true, w, 1);
}
}
for (auto it : used) {
dp[it] = inf;
}
for (auto it : adj[c]) {
int v = it.fi;
if (!processed[v]) {
centroid_decomposition(v);
}
}
}
int best_path(int _n, int _k, int h[][2], int l[]) {
n = _n;
k = _k;
for (int i = 0; i <= k; i ++) {
dp[i] = inf;
}
for (int i = 0; i < n - 1; i++) {
int u = h[i][0], v = h[i][1], w = l[i];
u++; v++;
adj[u].pb({v, w});
adj[v].pb({u, w});
}
centroid_decomposition(1);
return (ans == inf ? -1 : ans);
}
