#pragma GCC optimize("O3,unroll-loops")
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<
#define vi vector<int>
const int LIM = 2e5+1,inf = 2e18;
vector<pii> edges[LIM];
vi sz(LIM),taken(LIM,0);
int szs(int node,int p) {
sz[node] = 1;
for (auto it : edges[node]) {
if (it.first == p || taken[it.first]) continue;
sz[node]+=szs(it.first,node);
}
return sz[node];
}
int cent(int node,int p,int x) {
for (auto it : edges[node]) {
if (taken[it.first] || it.first == p) continue;
if (sz[it.first]*2 > x) return cent(it.first,node,x);
}
return node;
}
vector<pii> v;
void dist(int node,int p, int dep,int sm) {
v.push_back({sm,dep});
for (auto it : edges[node]) if (it.first != p) dist(it.first,node,dep+1,sm+it.second);
}
int ans = inf;
int mp[1000001];
int n,k;
void decompose(int node) {
int c = cent(node,node,szs(node,node));
taken[c] = 1;
mp[0] = 0;
vi seen;
for (auto it : edges[c]) {
if (taken[it.first]) continue;
dist(it.first,c,1,it.second);
for (auto itt : v) {
if (itt.first > k) continue;
ans = min(ans,itt.second+mp[k-itt.first]);
}
for (auto itt : v) {
if (itt.first > k) continue;
seen.push_back(itt.first);
mp[itt.first] = min(mp[itt.first],itt.second);
}
ans = min(ans,mp[k]);
v.clear();
}
for (auto it : seen) mp[it] = inf;
for (auto it : edges[c]) if (!taken[it.first]) decompose(it.first);
}
int32_t best_path(int32_t N, int32_t K, int32_t H[][2], int32_t L[])
{
for (int i=0;i<=K;i++) mp[i] = inf;
n = N,k = K;
for (int i=0;i<n-1;i++) {
edges[H[i][0]+1].push_back({H[i][1]+1,L[i]});
edges[H[i][1]+1].push_back({H[i][0]+1,L[i]});
}
decompose(1);
return ans == inf?-1:ans;
}
