/******************************
* author : @marvinthang *
* date : 15 / 01 / 2022 *
******************************/
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define superspeed ios_base::sync_with_stdio(false); cin.tie(nullptr); //cout.tie(nullptr);
#define file(name) if (fopen (name".inp", "r") ) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
#define REP(i, a, b) for (__typeof(a) i = (a) - ((a) > (b)); i != (b) - ((a) > (b)); i += ((a) > (b) ? -1 : 1))
#define FOR(i, a, b) for (__typeof(a) i = (a); i != (b) + ((a) > (b) ? -1 : 1); i += ((a) > (b) ? -1 : 1))
template <class U, class V> ostream & operator << (ostream& out, const pair<U, V> &p) { return out << '(' << p.first << ", " << p.second << ')'; }
template <class T> ostream & operator << (ostream &out, const vector<T> &vt) { out << '{'; for (size_t i = 0; i + 1 < vt.size(); i++) out << vt[i] << ", "; if (!vt.empty()) out << vt.back(); return out << '}'; }
void minimize(int &a, int b) { if (a > b) a = b; }
const int MOD = 1e9 + 7;
const double PI = 3.1415926535897932384626433832795; // acos(-1.0); atan(-1.0);
const int dir[] = {0, 1, 0, -1, 0}; // {0, 1, 1, -1, -1, 1, 0, -1, 0};
const long long oo = 1e18;
const int MAX = 2e5 + 5;
int N, K;
vector <pair <int, int>> adj[MAX];
int minPath[MAX * 10], newPath[MAX * 5], res;
vector <int> save, save2;
bool used[MAX];
void calc(int u, int par, int depth, int weight) {
if (weight > K) return;
res = min(res, minPath[K - weight] + depth);
newPath[weight] = min(newPath[weight], depth);
save.push_back(weight);
save2.push_back(weight);
for (pair <int, int> &x: adj[u]) {
int v = x.second, w = x.first;
if (v == par || used[v]) continue;
calc(v, u, depth + 1, weight + w);
}
}
int sizes[MAX];
int calcSize(int u, int par) {
sizes[u] = 1;
for (pair <int, int> &x: adj[u]) {
int v = x.second;
if (v == par || used[v]) continue;
sizes[u] += calcSize(v, u);
}
return sizes[u];
}
int findCentroid(int u, int par, int n) {
for (pair <int, int> &x: adj[u]) {
int v = x.second;
if (v == par || used[v]) continue;
if (sizes[v] > n / 2) return findCentroid(v, u, n);
}
return u;
}
void solve(int u) {
int n = calcSize(u, 0);
int centroid = findCentroid(u, 0, n);
used[centroid] = true;
save.clear();
for (pair <int, int> &x: adj[centroid]) {
int v = x.second, w = x.first;
if (used[v]) continue;
calc(v, centroid, 1, w);
for (int &x: save2) {
minPath[x] = min(minPath[x], newPath[x]);
newPath[x] = N + 1;
}
save2.clear();
}
res = min(res, minPath[K]);
for (int &x: save) minPath[x] = N + 1;
for (pair <int, int> &x: adj[centroid]) {
int v = x.second;
if (!used[v]) solve(v);
}
}
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], w = l[i];
++u; ++v;
adj[u].push_back( make_pair(w, v) );
adj[v].push_back( make_pair(w, u) );
}
res = 1e9;
fill(minPath, minPath + 1 + K, N + 1);
fill(newPath, newPath + 1 + K, N + 1);
solve(1);
if (res > N) res = -1;
return res;
}
