#include "race.h"
#include<bits/stdc++.h>
using namespace std;
int n,k,ans = INT_MAX;
vector<pair<int,int>> haha[200001];
vector<int> st(200001);
vector<bool> yeah(200001,true);
int dfs(int a, int t) {
int sb = 1;
for(int i = 0; i < haha[a].size(); i++) {
if(haha[a][i].first != t && yeah[haha[a][i].first]) {
sb+=dfs(haha[a][i].first,a);
}
}
st[a] = sb;
return sb;
}
void calc(map<int,int>& wut, int a, int d, int sb, int t) {
if(wut[k-sb] != 0 || k == sb) {
ans = min(ans,wut[k-sb]+d);
}
for(int i = 0; i < haha[a].size(); i++) {
if(yeah[haha[a][i].first] && haha[a][i].first != t) {
calc(wut,haha[a][i].first,d+1,sb+haha[a][i].second,a);
}
}
}
void update(map<int,int>& wut, int a, int d, int sb, int t) {
if(wut[sb] != 0) {
wut[sb] = min(wut[sb],d);
}
else {
wut[sb] = d;
}
for(int i = 0; i < haha[a].size(); i++) {
if(yeah[haha[a][i].first] && haha[a][i].first != t) {
update(wut,haha[a][i].first,d+1,sb+haha[a][i].second,a);
}
}
}
void dude(int a) {
dfs(a,-1);
int c = 0,p = a;
while(p != -1) {
c = p;
p = -1;
for(int i = 0; i < haha[c].size(); i++) {
if(yeah[haha[c][i].first] && st[c] > st[haha[c][i].first] && st[haha[c][i].first] > st[a]/2) {
p = haha[c][i].first;
}
}
}
map<int,int> wut;
wut[0] = 0;
for(int i = 0; i < haha[c].size(); i++) {
if(yeah[haha[c][i].first]) {
calc(wut,haha[c][i].first,1,haha[c][i].second,c);
update(wut,haha[c][i].first,1,haha[c][i].second,c);
}
}
yeah[c] = false;
for(int i = 0; i < haha[c].size(); i++) {
if(yeah[haha[c][i].first]) {
dude(haha[c][i].first);
}
}
yeah[c] = true;
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N;
k = K;
for(int i = 0; i < n-1; i++) {
haha[H[i][0]].push_back({H[i][1],L[i]});
haha[H[i][1]].push_back({H[i][0],L[i]});
}
dude(0);
if(ans == INT_MAX) {
ans = -1;
}
return ans;
}
