#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
template<class X, class Y>
inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
const int MAXN = 200005;
set<ii> G[MAXN];
int sz[MAXN], dp[5 * MAXN], numNode, pathLen;
int dfsSize(int u, int p) {
sz[u] = 1;
for (auto it : G[u]) {
int v(it.fi);
if(v != p)
sz[u] += dfsSize(v, u);
}
return sz[u];
}
int centroid(int u, int p, int nSize) {
for (auto it : G[u]) {
int v(it.fi);
if(v != p && sz[v] > nSize / 2)
return centroid(v, u, nSize);
}
return u;
}
int dfs(int u, int p, int len, int cntNode, vector<ii> &dis) {
if(len > pathLen)
return 1e9+7;
dis.push_back({len, cntNode + 1});
int res = min(int(1e9)+7, cntNode + dp[pathLen - len]);
for (auto it : G[u]) {
int v(it.fi), w(it.se);
if(v != p)
res = min(res, dfs(v, u, len + w, cntNode + 1, dis));
}
return res;
}
int build(int u, int p) {
int nSize = dfsSize(u, p);
int c = centroid(u, p, nSize);
dp[0] = 1;
int res(1e9+7);
vector<int> tmp;
for (auto it : G[c]) {
vector<ii> tmpn;
int v(it.fi), w(it.se);
res = min(res, dfs(v, c, w, 1, tmpn));
while(tmpn.size()) {
tmp.push_back(tmpn.back().fi);
minimize(dp[tmp.back()], tmpn.back().se);
tmpn.pop_back();
}
}
for (int it = 0; it < int(tmp.size()); ++it) {
int x(tmp[it]);
dp[x] = 1e9+7;
}
vector<ii> tmpg(G[c].begin(), G[c].end());
for (int it = 0; it < int(tmpg.size()); ++it) {
int v(tmpg[it].fi), w(tmpg[it].se);
G[c].erase({v, w});
G[v].erase({c, w});
res = min(res, build(v, c));
}
return res;
}
int best_path(int N, int K, int H[][2], int L[]) {
numNode = N, pathLen = K;
for (int i = 0; i + 1 < numNode; ++i) {
int u(H[i][0]), v(H[i][1]), w(L[i]);
G[u].insert({v, w});
G[v].insert({u, w});
}
for (int i = 0; i <= pathLen; ++i)
dp[i] = 1e9+7;
int res = build(0, -1);
return (res >= 1e9 ? -1 : res - 1);
}
