#include <bits/stdc++.h>
#include "race.h"
#define ii pair<int, int>
#define fi first
#define se second
#define sz(v) ((int)(v).size())
#define all(v) begin((v)), end(v)
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define dbg(x) "[" #x " = " << x << "]"
using namespace std;
const int MAXN = 2e5 + 5, infINT = 1e9 + 23737, MAXV = 1e6 + 5;
const int dx[4] = {-1, 0, 0, 1};
const int dy[4] = {0, -1, 1, 0};
template<class X, class Y> bool minimize(X &x, const Y &y){return x > y ? x = y, 1: 0;}
template<class X, class Y> bool maximize(X &x, const Y &y){return x < y ? x = y, 1: 0;}
int numNode, numReq, best[MAXV], sz[MAXN], res = MAXN + 1;
bool del[MAXN];
vector<ii> adj[MAXN];
vector<int> can;
void updateAns(int u, bool type, int sumDist, int step = 1, int par = 0){
if (sumDist > numReq) return;
can.push_back(sumDist);
if (type){
minimize(res, best[numReq - sumDist] + step);
}else{
minimize(best[sumDist], step);
}
for(ii x: adj[u]) if (x.fi != par && !del[x.fi]){
int v = x.fi, w = x.se;
updateAns(v, type, sumDist + w, step + 1, u);
}
}
int getSize(int u, int par = 0){
sz[u] = 1;
for(ii x: adj[u]) if (x.fi != par && !del[x.fi]){
int v = x.fi, w = x.se;
sz[u] += getSize(v, u);
}
return sz[u];
}
int getCentroid(int sizeU, int u, int par = 0){
for(ii x: adj[u]) if (x.fi != par && !del[x.fi]){
int v = x.fi, w = x.se;
if (sz[v] > (sizeU >> 1)) return getCentroid(sizeU, v, u);
}
return u;
}
void decomp(int u = 1){
int centroid = getCentroid(getSize(u), u);
del[centroid] = 1;
can.clear();
for(ii x: adj[centroid]) if (!del[x.fi]) {
int v = x.fi, w = x.se;
updateAns(v, true, w);
updateAns(v, false, w);
}
for(int sumDist: can) best[sumDist] = infINT;
for(ii x: adj[centroid]) if (!del[x.fi]){
int v = x.fi, w = x.se;
decomp(v);
}
}
int best_path(int N, int K, int edge[][2], int len[])
{
numNode = N; numReq = K;
for(int i = 0; i < numNode - 1; i++){
int u = edge[i][0] + 1, v = edge[i][1] + 1;
adj[u].push_back({v, len[i]});
adj[v].push_back({u, len[i]});
}
memset(best, 0x3f, sizeof best);
best[0] = 0;
decomp();
return (res <= MAXN ? res: -1);
}
