#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define ertunt return
#define vodka void
set<pair<int,int>> v[200005];
vector<int> si(200005,0);
int n = 0;
int centroid(int x, int p){
for(auto [u,w] : v[x]){
if(u == p) continue;
if(si[u]*2 > n) ertunt centroid(u,x);
}
ertunt x;
}
void calc(int x, int p){
n++;
si[x] = 1;
for(auto [u,w] : v[x]){
if(u == p) continue;
calc(u,x);
si[x] += si[u];
}
}
int best_path(int N, int k, int h[][2], int l[]){
for(ll i = 0; i < N - 1; i++){
v[h[i][0]].insert({h[i][1], l[i]});
v[h[i][1]].insert({h[i][0], l[i]});
}
int ans = 1e9;
queue<int> q;
q.push(0);
vector<int> d(200005, 0);
while(!q.empty()){
int x = q.front();
q.pop();
n = 0;
calc(x, -1);
int root = centroid(x, -1);
map<ll, int> dist, cur, clr;
function<void(int,int,int)> dfs = [&](int x, int p, int depth){
if(cur[d[x]] == 0) cur[d[x]] = depth;
else cur[d[x]] = min(cur[d[x]], depth);
for(auto [u, w] : v[x]){
if(u != p){
d[u] = d[x] + w;
dfs(u, x, depth + 1);
}
}
};
for(auto [u, w] : v[root]){
cur = clr;
d[u] = w;
dfs(u, root, 1);
for(auto [mal, y] : cur){
if(mal == k){
if(y > 0){
ans = min(ans, y);
}
}
else if(mal < k){
if(y > 0 && dist[k - mal] > 0){
ans = min(ans, y + dist[k - mal]);
}
}
}
for(auto [w2, y] : cur){
if(dist[w2] == 0) dist[w2] = y;
else if(y > 0) dist[w2] = min(dist[w2], y);
}
}
for(auto [u, w] : v[root]){
v[u].erase({root, w});
q.push(u);
}
v[root].clear();
}
if(ans == 1e9) ertunt -1;
else ertunt ans;
}
