#include <bits/stdc++.h>
using namespace std;
template<typename TH>
void _dbg(const char* sdbg, TH h)
{
cerr << sdbg << " = " << h << "\n";
}
template<typename TH, typename... TA>
void _dbg(const char* sdbg, TH h, TA... t)
{
while (*sdbg != ',') cerr << *sdbg++;
cerr << " = " << h << ",";
_dbg(sdbg + 1, t...);
}
#define db(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#define chkpt cerr << "--- Checkpoint here ---\n";
const int N=2e5+5,K=1e6+6,INF=1e9,LOG_N=20;
struct Edge{
int u,v,w;
int Adj(int x){
return u^v^x;
}
};
int n,k;
Edge edgeList[N];
vector<int> g[N];
bool del[N];
int sz[N],ans=INF,f[K];
void DFS_Size(int u,int fa){
sz[u]=1;
for(int id:g[u]){
int v=edgeList[id].Adj(u);
if(v!=fa&&!del[v]){
DFS_Size(v,u);
sz[u]+=sz[v];
}
}
}
int FindCentroid(int u,int fa,int curSz){
int maxSize=0,big=0;
for(int id:g[u]){
int v=edgeList[id].Adj(u);
if(v!=fa&&!del[v]&&sz[v]>maxSize){
maxSize=sz[v];
big=v;
}
}
if(maxSize<=curSz/2){
return u;
}
return FindCentroid(big,u,curSz);
}
void DFS_UpdateAns(int u,int fa,int64_t s,int d){
if(s<=k&&f[k-s]!=INF){
ans=min(ans,f[k-s]+d);
}
for(int id:g[u]){
int v=edgeList[id].Adj(u),w=edgeList[id].w;
if(!del[v]&&v!=fa){
DFS_UpdateAns(v,u,s+w,d+1);
}
}
}
void DFS_UpdateF(int u,int fa,int64_t s,int d){
if(s<=k){
f[s]=min(f[s],d);
}
for(int id:g[u]){
int v=edgeList[id].Adj(u),w=edgeList[id].w;
if(!del[v]&&v!=fa){
DFS_UpdateF(v,u,s+w,d+1);
}
}
}
void DFS_Reset(int u,int fa,int64_t s,int d){
if(s<=k){
f[s]=INF;
}
for(int id:g[u]){
int v=edgeList[id].Adj(u),w=edgeList[id].w;
if(!del[v]&&v!=fa){
DFS_Reset(v,u,s+w,d+1);
}
}
}
int BuildCentroidTree(int u){
DFS_Size(u,-1);
int cen=FindCentroid(u,-1,sz[u]);
for(int id:g[cen]){
int v=edgeList[id].Adj(cen),w=edgeList[id].w;
if(!del[v]){
f[0]=0;
DFS_UpdateAns(v,cen,w,1);
DFS_UpdateF(v,cen,w,1);
}
}
DFS_Reset(cen,cen,0,0);
del[cen]=true;
for(int id:g[cen]){
int v=edgeList[id].Adj(cen);
if(!del[v]){
int tmp=BuildCentroidTree(v);
// cout<<cen<<' '<<tmp<<'\n';
}
}
return cen;
}
int Solve(){
for(int i=0;i<K;++i){
f[i]=INF;
}
BuildCentroidTree(1);
return ans==INF?-1:ans;
}
int best_path(int N,int K,int H[][2],int L[])
{
n=N;
k=K;
for(int i=0;i<=n-2;++i){
int u=H[i][0]+1,v=H[i][1]+1;
g[u].push_back(i+1);
g[v].push_back(i+1);
edgeList[i+1]={u,v,0};
}
for(int i=0;i<=n-2;++i){
edgeList[i+1].w=L[i];
}
return Solve();
}
//int main()
//{
//// freopen("IOI11_race.inp","r",stdin);
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// cin>>n>>k;
// for(int i=1;i<=n-1;++i){
// int u,v,w;
// cin>>u>>v>>w;
// u++;
// v++;
//// cout<<u<<' '<<v<<'\n';
// g[u].push_back(i);
// g[v].push_back(i);
// edgeList[i]={u,v,w};
// }
//// for(int i=1;i<=n-1;++i){
//// cin>>edgeList[i].w;
//// }
// cout<<Solve();
// return 0;
//}
