#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define oset tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
const int N = 2e5 + 5;
vector<pair<int, int>> graph[N];
vector<pair<int, int>> res;
int k, sz[N], used[N];
int ans = 1e9;
void dfs(int v, int p){
sz[v] = 1;
for(auto &[u, w]: graph[v]){
if(u == p || used[u])continue;
dfs(u, v);
sz[v] += sz[u];
}
}
int get(int v, int p, int psz){
for(auto &[u, w]: graph[v]){
if(u != p && !used[u] && 2*sz[u] > psz)return get(u, v, psz);
}
return v;
}
void solve(int v, int p, int s, int cnt){
if(s > k || cnt > ans){
return;
}
res.push_back({s, cnt});
for(auto &[u, w]: graph[v]){
if(u == p || used[u])continue;
solve(u, v, s + w, cnt+1);
}
}
void decompose(int v){
dfs(v, -1);
v = get(v, -1, sz[v]);
used[v] = 1;
map<int, int> ps;
for(auto &[u, w]: graph[v]){
if(used[u])continue;
solve(u, v, w, 1);
for(auto &i: res){
if(ps.find(k - i.first) != ps.end()){
ans = min(ans, ps[k - i.first] + i.second);
}else if(i.first == k){
ans = min(ans, i.second);
}
}
for(auto &i: res){
if(ps.find(i.first) == ps.end()){
ps[i.first] = i.second;
}else{
ps[i.first] = min(ps[i.first], i.second);
}
}
res.clear();
}
for(auto &[u, w]: graph[v]){
if(!used[u])decompose(u);
}
}
int best_path(int n, int _, int h[][2], int l[]){
k = _;
for(int i = 0; i < n-1; i++){
graph[h[i][0]].push_back({h[i][1], l[i]});
graph[h[i][1]].push_back({h[i][0], l[i]});
}
memset(used, 0, sizeof used);
decompose(0);
return ans == 1e9 ? -1 : ans;
}
//int main(){
// ios::sync_with_stdio(false);
// cin.tie(0);
// //ifstream cin("inputf.txt");
// //ofstream cout("outputfv.txt");
// ll n; cin >> n;
// string s; cin >> s;
// vector<vector<ll>> dp(n, vector<ll>(n, 1e9));
// for(int i = n-1; i >= 0; i--){
// for(int j = 0; j < n; j++){
// if(i > j)dp[i][j] = 0;
// else if(i == j)dp[i][j] = 1;
// else{
// dp[i][j] = dp[i+1][j] + 1;
// for(int k = i + 1; k <= j; k++){
// if(s[i] == s[k]){
// dp[i][j] = min(dp[i][j], dp[i+1][k-1] + dp[k][j]);
// }
// }
// }
// }
// }
// cout << dp[0][n-1];
//}
