#include <bits/stdc++.h>
#include "race.h"
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
using namespace std;
using ll = long long;
using ii = pair<ll, ll>;
#define ff first
#define ss second
#define pb push_back
const int oo = 1e9 + 7;
int n, k;
vector<ii> adj[200001];
int sub[200001];
int res = oo;
int calc[1000001], mx;
bool rem[200001];
/// CENTROID DECOMPOSITION :
int dfs_size(int v, int p) {
sub[v] = 1;
for(auto u : adj[v]) {
if(u.ff == p || rem[u.ff]) continue;
sub[v] += dfs_size(u.ff, v);
}
return sub[v];
}
int centroid(int v, int p, int _n) {
for(auto u : adj[v]) {
if(u.ff == p || rem[u.ff]) continue;
if(sub[u.ff] >= _n)
return centroid(u.ff, v, _n);
}
return v;
}
void dfs(int v, int p, bool state, int curr, int len) {
if(len > k) return;
mx = max(mx, len);
if(state) calc[len] = min(calc[len], curr);
else res = min(res, curr + calc[k - len]);
for(auto u : adj[v]) {
if(u.ff == p || rem[u.ff]) continue;
dfs(u.ff, v, state, curr + 1, len + u.ss);
}
}
void build(int v = 0) {
int _n = dfs_size(v, -1) >> 1;
int c = centroid(v, -1, _n);
rem[c] = 1; mx = 0;
for(auto u : adj[c]) {
if(rem[u.ff]) continue;
dfs(u.ff, c, 0, 1, u.ss);
dfs(u.ff, c, 1, 1, u.ss);
}
fill(calc + 1, calc + mx + 1, oo);
for(auto u : adj[c]) {
if(rem[u.ff]) continue;
build(u.ff);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N, k = K;
for(int l = 0; l < n - 1; l++) {
int u = H[l][0], v = H[l][1], w = L[l];
adj[u].pb({v, w}); adj[v].pb({u, w});
}
fill(calc + 1, calc + 1000001, oo);
build();
return (res != oo ? res : -1);
}
