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