#include <bits/stdc++.h>
// #include "race.h"
#define endl '\n'
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define fo(i,n) for(auto i =0 ; i < n;i++)
#define fore(i,l,r) for(auto i = l; i < r;i++)
#define forex(i,r,l) for(auto i = r; i >= l; i--)
#define ffo(i,n) forex(i,n-1,0)
#define all(x) x.begin(),x.end()
#define lsb(x) x&(-x)
#define sz(x) (int)x.size()
#define gcd(a,b) __gcd(a,b)
#define vii vector<ii>
using namespace std;
using ii = pair<int,int>; using ll = long long; using ull = unsigned long long;
using vi = vector<ll>;
void valid(int in){cout<<((in)?"YES\n":"NO\n");return;}
const int N = 1e6 + 7;
vector<ii> graph[N];
bool vis[N];int ans = 1e9, sz[N], mn[N],k;
void find_sz(int nodo ,int p = -1){sz[nodo]=1;
for(auto [v, cost] : graph[nodo]){if(v==p || vis[v])continue;
find_sz(v,nodo);
sz[nodo] += sz[v];
}
}
int find_cent(int nodo, int raiz, int p = -1){
for(auto [v,cost] : graph[nodo]){if(v==p || vis[v])continue;
if(sz[v]>sz[raiz]/2)return find_cent(v, raiz, nodo);
}return nodo;
}
void dfs_calc(int nodo, int sum = 0,int nivel = 0, int p = -1){
if(sum>k)return;
ans = min(ans, mn[k-sum]+ nivel);
for(auto [v,cost] : graph[nodo]){if(v==p || vis[v])continue;
dfs_calc(v, sum + cost, nivel+1, nodo);
}
}
void dfs_add(int nodo, int sum = 0, int nivel = 0, int p = -1){
if(sum>k)return;
mn[sum] = min(mn[sum],nivel);
for(auto [v,cost] : graph[nodo]){if(v==p || vis[v])continue;
dfs_add(v, sum+cost, nivel+1, nodo);
}
}
void dfs_del(int nodo, int sum = 0, int nivel = 0, int p = -1){
if(sum>k)return;
mn[sum] =1e9;
for(auto [v,cost] : graph[nodo]){if(v==p || vis[v])continue;
dfs_del(v, sum+cost, nivel+1, nodo);
}
}
void solve(int nodo){
find_sz(nodo);int cen = find_cent(nodo,nodo);mn[0]=0;
// fo(i,k+2) cout << mn[i] << " "; cout << endl;
vis[cen]=1;
for(auto [v,cost] : graph[cen]){
if (vis[v]) continue;
dfs_calc(v, cost, 1,cen);
dfs_add(v,cost, 1,cen);
}
dfs_del(cen);
for(auto [v,cost] : graph[cen]) if (!vis[v]) solve(v);
}
int best_path(int n, int K, int H[][2], int L[]){k=K;fill(mn, mn+k+3, 1e9);
fo(i,n-1){
graph[H[i][0]].pb({H[i][1], L[i]});
graph[H[i][1]].pb({H[i][0], L[i]});
}solve(0);return (ans == 1e9 ? -1 : ans);
}
