#include <bits/stdc++.h>
#include "race.h"
#define ll long long
#define FOR(i,x,y) for(ll i=x; i<y; i++)
using namespace std;
bool r[300000];
vector<vector<ll>> edges[300000];
ll sub[300000];
ll n,m,root,k;
vector<vector<ll>> twosum;
ll ans = 1000000000;
ll dfs(ll a, ll p){
sub[a] = 1;
for (auto& i : edges[a]){
if (i[0]!=p && !r[i[0]]) sub[a] += dfs(i[0], a);
}
return sub[a];
}
void dfs2(ll a, ll p, ll v, ll num, ll col){
for (auto& i : edges[a]){
if (i[0]!=p && !r[i[0]]) dfs2(i[0], a, v+i[1], num+1, col);
}
twosum.push_back({v, num, col});
}
ll centroid(ll a, ll sz, ll p){
for (auto&i : edges[a]){
if (i[0]!=p && !r[i[0]] && sub[i[0]]*2 > sz){
return centroid(i[0], sz, a);
}
}
return a;
}
void decomp(ll a, ll p){
ll c = centroid(a, dfs(a, -1), -1);
twosum.clear();
ll col = 0;
for (auto&i : edges[c]){
if (!r[i[0]]) dfs2(i[0], c, i[1],1,col);
twosum.push_back({0,0,col});
col++;
}
sort(twosum.begin(), twosum.end());
ll lo = 0;
ll hi = twosum.size()-1;
while (lo<=hi){
if (twosum[lo][0] + twosum[hi][0] > k){
hi--;
}else if (twosum[lo][0] + twosum[hi][0] == k){
if (twosum[lo][2] == twosum[hi][2]){
if (twosum[hi][0] != twosum[hi-1][0]){
lo++;
continue;
}
hi--;
continue;
}else{
ans = min(ans, twosum[lo][1] + twosum[hi][1]);
hi --;
}
}else if (twosum[lo][0] + twosum[hi][0] < k){
lo++;
}
}
r[c] = 1;
for (auto&i : edges[c]){
if (!r[i[0]]) decomp(i[0], c);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N;
k = K;
FOR(i,0,n-1){
ll a,b,c;
a = H[i][0];
b = H[i][1];
c = L[i];
edges[a].push_back({b,c});
edges[b].push_back({a,c});
}
decomp(0,-1);
if (ans == 1000000000) ans = -1;
return ans;
}
