#include "race.h"
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL MOD = (LL)1e9 + 7;
const LL NS = (LL)2e5 + 4;
LL N, k;
vector<pair<LL, LL>> way[NS];
LL chk[NS], sz[NS], rt;
LL dis[(LL)1e6 + 4];
LL ans;
vector<LL> did;
vector<pair<LL, LL>> put;
void getroot(LL now, LL pr, LL alls){
sz[now] = 1;
LL f = 1;
for(auto&nxt:way[now]){
if(nxt.first == pr || chk[nxt.first]){
continue;
}
getroot(nxt.first, now, alls);
sz[now] += sz[nxt.first];
if(sz[nxt.first] > alls / 2){
f = 0;
}
}
if(f){
rt = now;
}
}
void getdis(LL now, LL ndis, LL pr, LL ndep){
LL need = k - ndis;
if(need >= 0){
ans = min(ans, ndep + dis[need]);
}
for(auto&nxt:way[now]){
if(nxt.first == pr || chk[nxt.first]){
continue;
}
getdis(nxt.first, ndis + nxt.second, now, ndep + 1);
}
if(ndis < (LL)1e6 + 4){
if(dis[ndis] > ndep){
put.push_back({ndis, ndep});
did.push_back(ndis);
}
}
}
void sol(LL now, LL alls){
dis[0] = 0;
chk[now] = 1;
did.clear();
for(LL i = 0; i < (LL)way[now].size(); ++i){
if(chk[way[now][i].first]){
continue;
}
getdis(way[now][i].first, way[now][i].second, now, 1);
while((LL)put.size()){
dis[put.back().first] = min(dis[put.back().first], put.back().second);
put.pop_back();
}
}
while((LL)did.size()){
dis[did.back()] = MOD;
did.pop_back();
}
for(auto&nxt:way[now]){
if(chk[nxt.first]){
continue;
}
LL nsz = (sz[nxt.first] > sz[now] ? alls - sz[now]:sz[nxt.first]);
getroot(nxt.first, now, nsz);
sol(rt, nsz);
}
}
int best_path(int n, int K, int H[][2], int L[])
{
for(LL i = 0; i < (LL)1e6 + 4; ++i){
dis[i] = MOD;
}
ans = MOD;
ios_base::sync_with_stdio(false);
cin.tie(NULL);
N = n, k = K;
for(LL i = 0; i < N - 1; ++i){
LL a, b, c;
a = H[i][0], b = H[i][1], c = L[i];
way[a].push_back({b, c}), way[b].push_back({a, c});
}
getroot(1, -1, N);
sol(rt, N);
if(ans == MOD){
return -1;
}
else{
return ans;
}
}
