#include <bits/stdc++.h>
#include "race.h"
#define fi first
#define se second
using namespace std;
using ii = pair<int,int>;
const int maxn = 2e5+5;
const int maxk = 1e6+5;
int res = 1e9 + 9;
int pos[maxk], sub[maxn];
bool num[maxn];
stack <int> st;
vector <ii> adj[maxn];
void dfs(int u,int p){
sub[u] = 1;
for (ii it : adj[u]){
if (it.fi == p || num[it.fi]) continue;
dfs(it.fi,u);
sub[u] += sub[it.fi];
}
}
int centroid(int u,int p,int n){
for (ii it : adj[u]){
if (it.fi == p || num[it.fi]) continue;
if (sub[it.fi] * 2 > n) return centroid(it.fi,u,n);
}
return u;
}
void getans(int u,int p,int cur,int km,int K,int type){
if (km > K) return;
if (!type){
res = min(res,cur + pos[K - km]);
} else{
pos[km] = min(pos[km],cur);
st.push(km);
}
for (ii it : adj[u]){
if (it.fi == p || num[it.fi]) continue;
getans(it.fi,u,cur + 1,km + it.se,K,type);
}
}
void solve(int u,int K){
dfs(u,0);
int m = sub[u];
int root = centroid(u,0,m);
num[root] = 1;
for (ii it : adj[root]){
if (num[it.fi]) continue;
getans(it.fi,root,1,it.se,K,0);
getans(it.fi,root,1,it.se,K,1);
}
while (!st.empty()){
pos[st.top()] = 1e9 + 9;
st.pop();
}
for (ii it : adj[root]){
if (num[it.fi]) continue;
solve(it.fi,K);
}
}
int best_path(int N, int K, int H[][2], int L[]){
for (int i = 0; i < N - 1; i++){
H[i][0]++; H[i][1]++;
adj[H[i][0]].push_back({H[i][1],L[i]});
adj[H[i][1]].push_back({H[i][0],L[i]});
}
for (int i = 1; i <= K; i++) pos[i] = 1e9 + 9;
solve(1,K);
return (res <= 0 || res > N ? -1 : res);
}
#ifdef LOCAL
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int N = 11, K = 12;
int H[10][2] = {{0,1},{0,2},{2,3},{3,4},{4,5},{0,6},{6,7},{6,8},{8,9},{8,10}};
int L[10] = {3,4,5,4,6,3,2,5,6,7};
cout << best_path(N, K, H, L) << '\n';
return 0;
}
#endif // LOCAL
/*
int N = 4, K = 3;
int H[3][2] = {{0,1},{1,2},{1,3}};
int L[3] = {1,2,4};
int N = 3, K = 3;
int H[2][2] = {{0,1},{1,2}};
int L[2] = {1,1};
int N = 11, K = 12;
int H[10][2] = {{0,1},{0,2},{2,3},{3,4},{4,5},{0,6},{6,7},{6,8},{8,9},{8,10}};
int L[10] = {3,4,5,4,6,3,2,5,6,7};
*/
