#include<bits/stdc++.h>
#include "race.h"
using namespace std;
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(), (a).end()
#define task "kbsiudthw"
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<int, ii> pii;
const int N = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 2277;
int n, ans = 1e9, sz[N], block[N], best[(int)(1e6) + 5], k;
vector<ii> G[N];
int get_subtree_size(int u, int par = 0){
sz[u] = 1;
for (ii &v : G[u]){
if (block[v.fi] || v.fi == par) continue;
sz[u] += get_subtree_size(v.fi, u);
}
return sz[u];
}
int get_centroid(int u, int sub_sz, int par = 0){
for (ii &v : G[u]){
if (v.fi == par || block[v.fi]) continue;
if (sz[v.fi] * 2 > sub_sz) return get_centroid(v.fi, sub_sz, u);
}
return u;
}
vector<ii> sub;
vi all;
void dfs(int u, int h, int dist, int par = 0){
if (dist > k) return;
sub.pb({dist, h});
ans = min(ans, h + best[k - dist]);
for (ii & v: G[u]){
if (v.fi == par || block[v.fi]) continue;
dfs(v.fi, h + 1, dist + v.se, u);
}
}
void Centroid(int u){
int centroid = get_centroid(u, get_subtree_size(u));
block[centroid] = 1;
best[0] = 0;
for (ii & v: G[centroid]){
if (block[v.fi]) continue;
dfs(v.fi, 1, v.se, u);
for (ii &x : sub){
if (best[x.fi] == 1e9) all.pb(x.fi);
best[x.fi] = min(best[x.fi], x.se);
}
sub.clear();
}
for (int &x : all) best[x] = 1e9;
all.clear();
for (ii &x : G[centroid]){
if (block[x.fi]) continue;
Centroid(x.fi);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
FOR (i, 1, K) best[i] = 1e9;
k = K;
FOR (i, 0, N - 2){
int u = H[i][0] + 1, v = H[i][1] + 1, w = L[i];
G[u].pb({v, w});
G[v].pb({u, w});
}
Centroid(1);
return (ans == 1e9 ? -1 : ans);
}
//int main(){
// ios_base::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
// cin >> n >> k;
// FOR (i, 0, k) best[i] = 1e9;
// FOR (i,1 , n - 1){
// int u, v, w; cin >> u >> v >> w;
// ++u; ++v;
// G[u].pb({v, w});
// G[v].pb({u, w});
// }
// Centroid(1);
// cout << ans;
//
//}
