#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>
using namespace std;
#define ALL(x) x.begin(), x.end()
#define N 200005
#define K 1000005
int n, k, sz[N], dead[N], z = 1e9, dp[K];
vector<pair<int, int>> g[N];
vector<int> accessed;
int dfs(int u, int p)
{
sz[u] = 1;
for (auto [w, v] : g[u]) if (v != p && !dead[v]) sz[u] += dfs(v, u);
return sz[u];
}
int get_centroid(int u, int p, int tn)
{
for (auto [w, v] : g[u]) if (v != p && !dead[v] && sz[v] * 2 >= tn) return get_centroid(v, u, tn);
return u;
}
void count(int u, int p, int fil, int dis, int dep)
{
if (dis > k) return;
accessed.push_back(dis);
if (fil) dp[dis] = min(dp[dis], dep);
else z = min(z, dp[k-dis] + dep);
for (auto [w, v] : g[u])
if (v != p && !dead[v]) count(v, u, fil, dis+w, dep+1);
}
void decomp(int u)
{
u = get_centroid(u, -1, dfs(u, -1));
dead[u] = 1;
dp[0] = 0;
for (auto [w, v] : g[u]) if (!dead[v]) count(v, u, 0, w, 1), count(v, u, 1, w, 1);
for (auto x : accessed) dp[x] = 1e9+40;
accessed.clear();
for (auto [w, v] : g[u]) if (!dead[v]) decomp(v);
}
int best_path(int n0, int k0, int h[][2], int l[])
{
memset(dp, 63, sizeof dp);
n=n0,k=k0;
for (int i = 0; i < n-1; ++i)
{
int u = h[i][0], v = h[i][1], w=l[i];
g[u].emplace_back(w, v), g[v].emplace_back(w, u);
}
decomp(0);
return (z < 1e9) ? z : -1;
}
