#include <algorithm>
#include <vector>
#include <map>
using namespace std;
using pii = pair<int, int>;
const int N = 200005, INF = 2e9 + 11;
int k;
vector<pii> adj[N];
int sz[N];
bool del[N];
int ans = INF;
vector<pii> dist;
int Size(int x, int t = -1)
{
sz[x] = 1;
for (auto [y, _] : adj[x])
if (y != t && !del[y])
sz[x] += Size(y, x);
return sz[x];
}
int Centroid(int x, int size, int t = -1) {
for (auto [y, _] : adj[x])
{
if (y == t || del[y]) continue;
if (sz[y] * 2 > size)
return Centroid(y, size, x);
}
return x;
}
void DfsDists(int x, int t, int we, int d)
{
if (we > k || d > ans) return;
dist.emplace_back(we, d);
for (auto [y, w] : adj[x])
{
if (y == t || del[w]) continue;
DfsDists(y, x, we + w, d + 1);
}
}
void BuildCentroidTree(int x)
{
int cen = Centroid(x, Size(x));
map<int, int> mp; // mp[dist] = lung_min
for (auto [y, w] : adj[cen])
{
if (del[y]) continue;
DfsDists(y, cen, w, 1);
for (auto [we, d] : dist)
{
if (mp.find(k - we) != mp.end())
ans = min(ans, mp[k - we] + d);
else if (we == k)
ans = min(ans, d);
}
for (auto [we, d] : dist)
{
if (mp.find(we) == mp.end())
mp[we] = d;
else
mp[we] = min(mp[we], d);
}
dist.clear();
}
del[cen] = 1;
for (auto [x, _] : adj[cen])
{
if (del[x]) continue;
BuildCentroidTree(x);
}
}
int best_path(int n, int k, int h[][2], int l[])
{
::k = k;
for (int i = 0, x, y, w; i < n - 1; i++)
{
x = h[i][0], y = h[i][1], w = l[i];
adj[x].emplace_back(y, w);
adj[y].emplace_back(x, w);
}
BuildCentroidTree(0);
return ans == INF ? -1 : ans;
}
