/*
Author: baodat
※\(^o^)/※
Current goal: Training for VNOI shirt
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, l, r) for(int i = l; i <= r; i++)
#define FORD(i, l, r) for(int i = l; i >= r; i--)
#define db double
#define ldb long double
#define all_1(x) (x).begin() + 1, (x).end()
#define all(x) (x).begin(), (x).end()
#define ins insert
#define pb push_back
template<typename T>void debug_var(const T& var, const string& name){
cerr << name << ": " << var << "\n";
}
template<typename T>void debug_1d(const T& vt, const string& name){
if(vt.empty()){
cerr << name << " is empty!\n";
return;
}
FOR(i, 0, (int)vt.size() - 1){
cerr << name << "[" << i << "]: " << vt[i] << "\n";
}
}
const ll oo = 2e18;
const int N = 2e5 + 5;
const int K = 1e6 + 5;
int freq[K], n, k;
vector<pair<int, int>> adj[N];
bool removed[N];
int subtree_sz[N];
void dfs(int u, int p){
subtree_sz[u] = 1;
for(auto [v, w] : adj[u]){
if(v == p || removed[v]) continue;
dfs(v, u);
subtree_sz[u] += subtree_sz[v];
}
}
int find_centroid(int u, int p, int cur_sz){
for(auto [v, w] : adj[u]){
if(v == p || removed[v]) continue;
if(subtree_sz[v] > cur_sz / 2) return find_centroid(v, u, cur_sz);
}
return u;
}
int ans = 1e9;
void get_cur_path(vector<pair<int ,int>>& cur_path, int u, int p, int cur_depth, int cur_w){
if(cur_w > k) return;
cur_path.pb({cur_depth, cur_w});
for(auto [v, w] : adj[u]){
if(v == p || removed[v]) continue;
get_cur_path(cur_path, v, u, cur_depth + 1, cur_w + w);
}
}
void centroid_decompose(int u){
dfs(u, -1);
int cur_centroid = find_centroid(u, -1, subtree_sz[u]);
removed[cur_centroid] = true;
vector<int> ds; //save what changed
ds.pb(0);
freq[0] = 0;
for(auto [v, w] : adj[cur_centroid]){
if(removed[v]) continue;
vector<pair<int, int>> cur_path;
get_cur_path(cur_path, v, -1, 1, w);
for(auto[cur_depth, cur_w] : cur_path){
ans = min(ans, cur_depth + freq[k - cur_w]);
}
//update
for(auto[cur_depth, cur_w] : cur_path){
if(cur_depth < freq[cur_w]){
freq[cur_w] = cur_depth;
ds.pb(cur_w);
}
}
}
for(int it : ds){
freq[it] = 1e9;
}
for(auto [v, w] : adj[cur_centroid]){
if(removed[v]) continue;
centroid_decompose(v);
}
}
int best_path(int _n, int _k, int h[][2], int l[]){
FOR(i, 0, K - 1) freq[i] = 1e9;
n = _n;
k = _k;
FOR(i, 0, n - 2){
++h[i][0];
++h[i][1];
adj[h[i][0]].pb({h[i][1], l[i]});
adj[h[i][1]].pb({h[i][0], l[i]});
}
centroid_decompose(1);
return (ans == 1e9 ? -1 : ans);
}
