#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define bitcount __builtin_popcountll
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree<long long, null_type,less_equal<long long>,rb_tree_tag,tree_order_statistics_node_update>;
const int N = 2e5 + 5;
vector<pair<int, long long>> g[N];
int sz[N], is_removed[N];
int k, ans = 1e9, n;
map<long long, int> cnt;
int get_sz(int u, int p)
{
sz[u] = 1;
for (auto [v, _] : g[u])
{
if (v == p || is_removed[v])
continue;
sz[u] += get_sz(v, u);
}
return sz[u];
}
int get_cent(int u, int p, int cur_sz)
{
for (auto [v, _] : g[u])
{
if (v == p || is_removed[v])
continue;
if (sz[v] * 2 > cur_sz)
return get_cent(v, u, cur_sz);
}
return u;
}
void dfs(int v, int p, int depth, int delta, long long w)
{
if(cnt.count(w))
cnt[w] = min(cnt[w], depth);
else cnt[w] = depth;
for (auto [u, W] : g[v])
{
if (u == p || is_removed[u])
continue;
dfs(u, v, depth + 1, delta, w + W);
}
}
void get_ans(int u, int p, int depth, long long w)
{
if (k - w >= 0 && cnt.count(k - w))
ans = min(ans, cnt[k - w] + depth);
for (auto [v, W] : g[u])
{
if (v == p || is_removed[v])
continue;
get_ans(v, u, depth + 1, W + w);
}
}
void comp(int v)
{
int size = get_sz(v, -1), cent = get_cent(v, -1, size);
cnt[0] = 0;
for (auto [u, w] : g[cent])
{
if (is_removed[u])
continue;
get_ans(u, cent, 1, w);
dfs(u, cent, 1, 1, w);
}
cnt.clear();
is_removed[cent] = 1;
for (auto [u, _] : g[cent])
{
if (is_removed[u])
continue;
comp(u);
}
}
// int32_t main()
// {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// cout.tie(nullptr);
// cin >> n >> k;
// for(int i = 0; i < n - 1; i++){
// int u, v, w; cin >> u >> v >> w;
// g[u].push_back({v, w});
// g[v].push_back({u, w});
// }
// comp(0);
// cout << ans;
// return 0;
// }
int best_path(int _n, int _k, int h[][2], int l[]) {
n = _n;
k = _k;
for (int i = 0; i < n-1; i++) {
g[h[i][0]].emplace_back(h[i][1], l[i]);
g[h[i][1]].emplace_back(h[i][0], l[i]);
}
comp(0);
return ans == 1e9 ? -1 : ans;
}
