#include <bits/stdc++.h>
#include "race.h"
using namespace std;
#define name "race"
#define MAXN 200005
#define pb push_back
#define pf push_front
#define ll long long
#define ii pair<int, int>
#define fs first
#define sc second
#define ill pair<int, ll>
#define lli pair<ll, int>
#define llll pair<ll, ll>
#define all(v) v.begin(),v.end()
#define uni(v) v.erase(unique(all(v)),v.end())
#define bit(n,i) (((n)>>(i))&1)
#define FOR(i,a,b) for (int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for (int i=(a),_b=(b); i>=_b; i--)
#define MASK(i) (1LL<<(i))
const int INF=1e9;
const int MOD=1e9+7;
void add(int &u, int v){
u+=v;
if (u>=MOD) u-=MOD;
}
void sub(int &u, int v){
u-=v;
if (u<0) u+=MOD;
}
void minimize(int &u, int v){
u=min(u,v);
}
void maximize(int &u, int v){
u=max(u,v);
}
long long Rand(long long l, long long r){
ll tmp=0;
FOR(i,1,4) tmp=((tmp<<15)^(((1<<15)-1)&rand()));
return l+tmp%(r-l+1);
}
int n,k;
vector<ii> adj[MAXN];
namespace sub2{
int dfs(int u, int p, int d, int w){
if (w>k) return INF;
if (w==k) return d;
int kq=INF;
for (ii pairs:adj[u]){
int v=pairs.fs;
int wei=pairs.sc;
if (v==p) continue;
minimize(kq,dfs(v,u,d+1,w+wei));
}
return kq;
}
int solve(){
int res=INF;
FOR(i,1,n){
minimize(res,dfs(i,0,0,0));
}
return (res==INF?-1:res);
}
}
namespace sub3{
int sz[MAXN];
bool del[MAXN];
int get_sz(int u, int p){
sz[u]=1;
for (ii pairs:adj[u]){
int v=pairs.fs;
if (del[v]||v==p) continue;
sz[u]+=get_sz(v,u);
}
return sz[u];
}
int centroid(int u, int p, int n){
for (ii pairs:adj[u]){
int v=pairs.fs;
if (v==p||del[v]) continue;
if (2*sz[v]>n) return centroid(v,u,n);
}
return u;
}
int kq;
set<ii> se;
void update(int type, int u, int p, int d, int w){
if (w>k) return;
if (type==0){
//minmize(ans,d+mp[k-w]);
auto it=se.lower_bound((ii){k-w,0});
if (it!=se.end()){
ii tmp=(*it);
if (tmp.fs==k-w){
minimize(kq,tmp.sc+d);
}
}
}
else{
se.insert({w,d});
}
for (ii pairs:adj[u]){
int v=pairs.fs;
int wei=pairs.sc;
if (v==p||del[v]) continue;
update(type,v,u,d+1,w+wei);
}
}
void calc(int u){
int c=centroid(u,-1,get_sz(u,-1));
del[c]=1;
se.insert((ii){0,0});
for (ii pairs:adj[c]){
int v=pairs.fs;
int wei=pairs.sc;
if (del[v]) continue;
update(0,v,c,1,wei);
update(1,v,c,1,wei);
}
se.clear();
for (ii pairs:adj[c]){
int v=pairs.fs;
if (del[v]) continue;
calc(v);
}
}
int solve(){
kq=INF;
calc(1);
return (kq==INF?-1:kq);
}
}
int best_path(int N, int K, int H[][2], int L[]){
FOR(i,0,N-2){
int u=H[i][0];
int v=H[i][1];
++u;
++v;
int w=L[i];
adj[u].pb({v,w});
adj[v].pb({u,w});
}
n=N;
k=K;
if (N<=1000) return sub2::solve();
else
return sub3::solve();
}
