#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
#define ar array
#define all(x) x.begin(),x.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;
bool remender(ll a , ll b){return a%b;}
const int N = 200002;
vector<pair<int,int>> adj[N];
int k;
int siz[N];
bool vis[N];
int cnt[1000003];
int ans;
vector<int> v;
void subtree(int node , int par = -1){
siz[node] = 1;
for(auto i : adj[node]){
if(!vis[i.vf] && i.vf != par){
subtree(i.vf , node);
siz[node] += siz[i.vf];
}
}
}
int get(int node , int par , int need){
for(auto i : adj[node]){
if(!vis[i.vf] && i.vf != par && siz[i.vf] > need){
return get(i.vf , node , need);
}
}
return node;
}
void cal(int node , int par , int depth , int cur , int fill){
if(cur > k)return;
if(fill){
ans = min(ans , depth + cnt[k - cur]);
}
else {
cnt[cur] = min(cnt[cur] , depth);
v.pb(cur);
}
for(auto i : adj[node]){
if(!vis[i.vf] && i.vf != par){
cal(i.vf , node , depth + 1 , i.vs + cur , fill);
}
}
}
void centriod(int node){
subtree(node);
int cen = get(node , -1 , siz[node]/2);
cnt[0] = 0;
v.clear();
for(auto i : adj[cen]){
if(!vis[i.vf]){
cal(i.vf , cen , 1 , i.vs , 1);
cal(i.vf , cen , 1 , i.vs , 0);
}
}
//cout << cen << ' ' << ans << '\n';
for(int i : v)cnt[i] = 1e9;
vis[cen] = 1;
for(auto i : adj[cen]){
if(!vis[i.vf]){
centriod(i.vf);
}
}
}
int best_path(int n , int k1 , int h[][2], int l[]){
for(int i = 0; i < n-1; i++){
adj[h[i][0]].pb(mp(h[i][1] , l[i]));
adj[h[i][1]].pb(mp(h[i][0] , l[i]));
}
k = k1;
memset(vis,0,sizeof vis);
for(int i = 0; i <= k; i++){
cnt[i] = 1e9;
}
ans = 1e9;
centriod(0);
return(ans == 1e9 ? -1 : ans);
}
