#include "race.h"
#include <bits/stdc++.h>
using namespace std;
struct edge{
int to, w;
};
int n, k;
vector<vector<edge>> v;
int ans = 1e9;
vector<bool> voltcentroid;
vector<int> siz;
map<int, int> m;
int szamoz(int x, int p = -1){
siz[x] = 1;
for(edge&i : v[x]){
if(!voltcentroid[i.to] && i.to != p){
siz[x] += szamoz(i.to, x);
}
}
return siz[x];
}
int keres(int x, int meret, int p = -1){
for(edge&i : v[x]){
if(!voltcentroid[i.to] && i.to != p && siz[i.to] > meret/2){
return keres(i.to, meret, x);
}
}
return x;
}
void szamol(int x, int w, int d, int p, bool update){
int cel = k-w;
if (update) {
if (m.count(w)) {
m[w] = min(m[w], d);
} else {
m[w] = d;
}
} else {
if(m.count(cel)){
ans = min(ans, m[cel] + d);
}
}
for(edge&i : v[x]){
if(!voltcentroid[i.to] && i.to != p){
szamol(i.to, min(1000000+1, w + i.w), d+1, x, update);
}
}
}
void solve(int x = 0){
int meret = szamoz(x);
int centroid = keres(x, meret);
m.clear();
m[0] = 0;
for(edge&i : v[centroid]){
if(!voltcentroid[i.to]){
szamol(i.to, i.w, 1, centroid, false);
szamol(i.to, i.w, 1, centroid, true);
}
}
voltcentroid[centroid] = true;
for(edge&i : v[centroid]){
if(!voltcentroid[i.to]){
solve(i.to);
}
}
}
int best_path(int N, int K, int H[][2], int L[]){
n = N;
k = K;
v.assign(n, {});
for(int i = 0; i < n-1; i++){
int a = H[i][0], b = H[i][1], w = L[i];
v[a].push_back({b, w});
v[b].push_back({a, w});
}
voltcentroid.assign(n, 0);
siz.assign(n, 0);
solve();
return ans == 1e9 ? -1 : ans;
}
