#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
#define ff first
#define ss second
const int maxn = 2e5 + 10;
map<long long,int> mp[maxn];
int n;
long long k;
vector <ii> adj[maxn];
int s[maxn],dau[maxn];
int ans = 1e9;
int get_sz(int x, int p)
{
s[x]=1;
for (ii i:adj[x])
if (i.ff!=p&&!dau[i.ff]) s[x]+=get_sz(i.ff,x);
return s[x];
}
int find_centroid(int x, int p, int sz)
{
for (ii i:adj[x])
if (i.ff!=p&&!dau[i.ff]&&s[i.ff]*2>sz) return find_centroid(i.ff,x,sz);
return x;
}
void dfs(int root, int x, int p, long long val, int depth)
{
if (val<=k&&mp[root][k-val]) ans=min(ans,depth+mp[root][k-val]);
if (val==k) ans=min(ans,depth);
for (ii i:adj[x])
if (i.ff!=p&&!dau[i.ff]) dfs(root,i.ff,x,1LL*val+i.ss,depth+1);
}
void dfs2(int root, int x, int p, long long val, int depth)
{
if (val<=k)
{
if (!mp[root][val]) mp[root][val] = depth;
else mp[root][val]=min(mp[root][val],depth);
}
for (ii i:adj[x])
if (i.ff!=p&&!dau[i.ff]) dfs2(root,i.ff,x,1LL*val+i.ss,depth+1);
}
void decompose(int x)
{
x=find_centroid(x,x,get_sz(x,x));
dau[x]=1;
for (ii i:adj[x])
if (!dau[i.ff])
{
dfs(x,i.ff,x,1LL*i.ss,1);
dfs2(x,i.ff,x,1LL*i.ss,1);
}
for (ii i:adj[x])
if (!dau[i.ff]) decompose(i.ff);
}
ii e[maxn];
int best_path(int N, int K, int H[][2], int L[])
{
n=N; k=K;
for (int i=0; i<n-1; i++)
{
e[i].ff=H[i][0];
e[i].ss=H[i][1];
}
for (int i=0; i<n-1; i++)
{
int w=L[i];
int u=e[i].ff; int v=e[i].ss;
u++; v++;
adj[u].push_back({v,w});
adj[v].push_back({u,w});
}
decompose(1);
if (ans==1e9) ans=-1;
return ans;
}
