#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include <bits/stdc++.h>
using namespace std;
const int N = 1<<18, INF = 1e9;
int k, x, y, ans = INF, dp[1<<20], sub[N];
array<int,2> a[N];
array<int,4> d[N];
vector<array<int,2>> e[N];
bitset<N> b;
void subDfs(int c)
{
a[0]={c,-1};
for (int i=0;i<x;++i)
{
sub[a[i][0]]=1;
for (auto j : e[a[i][0]])
if (j[0]!=a[i][1]&&!b[j[0]])
a[x++]={j[0],a[i][0]};
}
for (int i=x-1;i>0;--i)
sub[a[i][1]]+=sub[a[i][0]];
}
int findC(int c, int p, int t)
{
bool ok;
while (1)
{
ok=1;
for (auto i : e[c])
if (i[0]!=p&&!b[i[0]]&&sub[i[0]]>t)
{
p=c;
c=i[0];
ok=0;
break;
}
if (ok)
return c;
}
}
void dfs(int c, int p, int h)
{
int z=1,t;
d[0]={c,p,h,1};
for (int i=0;i<z;++i)
{
c=d[i][0];p=d[i][1];h=d[i][2];t=d[i][3];
a[x++]={h,t};
ans=min(ans,dp[k-h]+t);
for (auto j : e[c])
if (j[0]!=p&&h+j[1]<=k)
d[z++]={j[0],c,h+j[1],t+1};
}
}
void solve(int n)
{
x=1;
subDfs(n);
int c = findC(n,-1,sub[n]/2);
b[c]=1;
x=0;
for (auto i : e[c])
if (!b[i[0]]&&i[1]<=k)
{
y=x;
dfs(i[0],c,i[1]);
for (int j=y;j<x;++j)
dp[a[j][0]]=min(dp[a[j][0]],a[j][1]);
}
for (int i=0;i<x;++i)
dp[a[i][0]]=INF;
for (auto i : e[c])
if (!b[i[0]])
solve(i[0]);
}
int best_path(int n, int K, int h[][2], int l[])
{
k=K;
for (int i=0;i<n-1;++i)
{
e[h[i][0]].push_back({h[i][1],l[i]});
e[h[i][1]].push_back({h[i][0],l[i]});
}
for (int i=1;i<=k;++i)
dp[i]=INF;
solve(0);
if (ans==INF)
return -1;
return ans;
}
