#include <bits/stdc++.h>
#define ll long long
#define pi pair<int, int>
#define fi first
#define se second
using namespace std;
const int Nmax = 2e5 + 55;
const ll inf = 1e9;
bool vis[Nmax];
int N, K, subTree[Nmax], cnt[1000055];
int bestWay = inf;
vector<pi> edges[Nmax];
int dfs_sz(int u, int p)
{
subTree[u] = 1;
for(auto [v, w] : edges[u])
{
if (v == p || vis[v]) continue;
subTree[u] += dfs_sz(v, u);
}
return subTree[u];
}
int find_centroid(int u, int p, int ct)
{
for(auto [v, w] : edges[u])
{
if (v == p || vis[v]) continue;
if (!vis[v] && subTree[v] * 2 > ct)
{
return find_centroid(v, u, ct);
}
}
return u;
}
void dfs(int u, int p, int tot, int deep, bool contri)
{
if (tot > K) return;
if (contri)
{
if (cnt[K - tot] != -1)
{
bestWay = min(bestWay, cnt[K - tot] + deep);
}
} else
{
if (cnt[tot] != -1) cnt[tot] = min(cnt[tot], deep);
else cnt[tot] = deep;
}
for(auto [v, w] : edges[u])
{
if (v == p || vis[v]) continue;
dfs(v, u, tot + w, deep + 1, contri);
}
}
void process(int u, int p)
{
cnt[0] = 0;
for(auto [v, w] : edges[u])
{
if (v == p || vis[v]) continue;
dfs(v, u, w, 1, true);
dfs(v, u, w, 1, false);
}
}
void del(int u, int p, int tot)
{
if (tot > K) return;
cnt[tot] = -1;
for(auto [v, w] : edges[u])
{
if (v == p || vis[v]) continue;
del(v, u, tot + w);
}
}
void centroid_decompose(int u, int p)
{
dfs_sz(u, p);
int centroid = find_centroid(u, p, subTree[u]);
vis[centroid] = true;
process(centroid, p);
for(auto [v, w] : edges[centroid])
{
if (v == p || vis[v]) continue;
del(v, centroid, w);
}
for(auto [v, w] : edges[centroid])
{
if (v == p || vis[v]) continue;
centroid_decompose(v, centroid);
}
}
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];
edges[u].push_back({v, l[i]});
edges[v].push_back({u, l[i]});
}
memset(cnt, -1, sizeof(cnt));
centroid_decompose(0, -1);
return (bestWay == inf ? -1 : bestWay);
}
