#include <iostream>
#include <vector>
#include <map>
using namespace std;
const int N1=2e5+10;
const int inf=4e5;
int n,k,ans=inf;
vector<pair<int,int>> ma[N1];
int sz[N1];
bool done_for[N1];
void dfs_sz(int x,int p=-1)
{
sz[x]=1;
for(auto [y,w]:ma[x])
if(y!=p)
{
dfs_sz(y,x);
sz[x]+=sz[y];
}
}
int current_n=0;
int find_centroid(int x,int p=-1)
{
for(auto [y,w]:ma[x])
{
if(!done_for[y] and y!=p and sz[y]>(current_n/2))
{
sz[x]-=sz[y];
sz[y]+=sz[x];
return find_centroid(y,x);
}
}
return x;
}
map<int,int> tmp;
void dfs_update(int x,long long su=0,int h=1,int p=-1)
{
if(su>k)
return;
if(tmp.find(k-su)!=tmp.end())
ans=min(ans,tmp[k-su]+h);
for(auto [y,w]:ma[x])
if(y!=p and !done_for[y])
dfs_update(y,su+w,h+1,x);
}
void dfs_add(int x,long long su=0,int h=1,int p=-1)
{
if(su>k)
return;
if(tmp.find(su)==tmp.end())
tmp[su]=h;
else
tmp[su]=min(tmp[su],h);
for(auto [y,w]:ma[x])
{
if(y!=p and !done_for[y])
{
dfs_add(y,su+w,h+1,x);
}
}
}
void solve(int x,int p=-1,int l=0)
{
int c=find_centroid(x);
done_for[c]=1;
// Full working so now we do dfs
// What we do is the we go
tmp.clear();
tmp[0]=0;
for(auto [y,w]:ma[c])
{
if(!done_for[y])
{
dfs_update(y,w,1,-1);
dfs_add(y,w,1,-1);
}
}
for(auto [y,w]:ma[c])
{
if(!done_for[y])
{
current_n=sz[y];
solve(y,c,l+1);
}
}
}
int best_path(int n1, int k1, int h[][2], int l[])
{
n=n1;
k=k1;
for(int i=0;i<(n-1);i++)
{
ma[h[i][0]].push_back({h[i][1],l[i]});
ma[h[i][1]].push_back({h[i][0],l[i]});
}
dfs_sz(0);
current_n=n;
solve(0);
if(ans==inf)
ans=-1;
return ans;
}
