//gm --- akezhon
#include <bits/stdc++.h>
// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define pb push_back
#define pf push_front
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define pii pair<int,int>
#define tm (tl+tr)/2
#define TL v+v, tl, tm
#define TR v+v+1, tm+1, tr
#define DA l <= tl && tr <= r
#define NE r < tl || tr < l
#define double long double
//#define int long long
using namespace std;
const int nN=3e5+7;
const int mod=998244353;
const int inf=2e9;
vector <pii> g[nN];
int sz[nN];
bool del[nN];
int n, k;
map<int,int>mp;
int ans;
int cent(int v, int par, int s){
for(auto [u, col] : g[v]){
if(u != par && del[u] == 0 && sz[u]*2 > s)return cent(u, v, s);
}
return v;
}
void get_sz(int v, int par){
sz[v] = 1;
for(auto [u, col] : g[v]){
if(u != par && del[u] == 0){
get_sz(u, v);
sz[v] += sz[u];
}
}
}
void get(int v, int p, int a, int b){
if(a > k)return;
if(a==k)ans = min(ans, b);
else if(mp[k-a])ans = min(ans, b+mp[k-a]);
for(auto [u, col] : g[v]){
if(del[u] == 1 || u == p)continue;
get(u, v, a+col, b+1);
}
}
void add(int v, int p, int a, int b){
if(a > k)return;
if(mp[a] == 0){
if(a)mp[a] = b;
}
else mp[a] = min(mp[a], b);
for(auto [u, col] : g[v]){
if(del[u] == 1 || u == p)continue;
add(u, v, a+col, b+1);
}
}
void build(int v){
get_sz(v, v);
v = cent(v, v, sz[v]);
del[v] = 1;
mp.clear();
mp[0] = 0;
for(auto [u, col] : g[v]){
if(del[u] == 1)continue;
get(u, v, col, 1);
add(u, v, col, 1);
}
for(auto [u, col] : g[v]){
if(del[u] == 0)build(u);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
k=K;
for(int i=0; i < N-1; i++){
int a = H[i][0], b = H[i][1], col = L[i];
g[a].pb({b, col});
g[b].pb({a, col});
}
ans = 1e9;
build(0);
if (ans == 1e9)ans = -1;
return ans;
}
