#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define pb push_back
#define f first
#define s second
typedef long long ll;
typedef pair<int, int> pii;
const int MAXN = 200100, MAXK = 21;
int n, k;
vector<pii> adj[MAXN];
ll pref[MAXN];
int par[MAXN][MAXK];
int dep[MAXN];
void dfs1 (int v, int p) {
FOR(i, 1, MAXK-1) {
par[v][i] = par[par[v][i-1]][i-1];
}
for(auto pp : adj[v]) {
int u = pp.f;
ll w = pp.s;
if (u == p) continue;
pref[u] = pref[v] + w;
par[u][0] = v;
dep[u] = dep[v]+1;
dfs1 (u, v);
}
}
int lca (int u, int v) {
if (u == v) return u;
if (dep[u] > dep[v]) swap(u,v);
int d = dep[v] - dep[u];
FOR(i, 0, MAXK-1)
if (d & (1<<i))
v = par[v][i];
if (u == v) return u;
for (int i = MAXK-1; i >= 0; i--) {
if (par[v][i] != par[u][i]) {
v = par[v][i];
u = par[u][i];
}
}
return par[u][0];
}
ll d (int u, int v) {
return pref[u] + pref[v] - 2*pref[lca(u,v)];
}
int d2 (int u, int v) {
return dep[u] + dep[v] - 2*dep[lca(u,v)];
}
int sub2 () {
dfs1 (1, -1);
int ans = -1;
FOR(i, 1, n) FOR(j, 1, n) {
if (d(i,j) == k) {
int cur = d2(i,j);
if (ans == -1) ans = cur;
else ans = min(ans, cur);
}
}
return ans;
}
int dp[MAXN][110], dp2[MAXN][110];
int ans2 = -1;
void dfs2 (int v, int p) {
dp[v][0] = 0;
dp2[v][0] = 0;
for(auto pp : adj[v]) {
int u = pp.f;
ll w = pp.s;
if (u == p) continue;
dfs2 (u, v);
/// search for ans
FOR(i, 0, k) {
if (i + w > k) continue;
if (dp[u][i] == -1) continue;
int cur = dp[u][i];
if (dp2[v][k-i-w] == -1) continue;
//cout << " searching v = " << v << " u = " << u << " i = " << i << endl;
int cur2 = cur + dp2[v][k-i-w] + 1;
if (ans2 == -1) ans2 = cur2;
else ans2 = min(ans2, cur2);
}
/// upd dp and dp2
FOR(i, 0, k) {
if (i + w > k) continue;
if (dp[u][i] == -1) continue;
int cur = dp[u][i] + 1;
if (dp[v][i+w] == -1) dp[v][i+w] = cur;
else dp[v][i+w] = min(dp[v][i+w], cur);
if (dp2[v][i+w] == -1) dp2[v][i+w] = cur;
else dp2[v][i+w] = min(dp2[v][i+w], cur);
}
}
//cout << " v = " << v << endl;
//FOR(i, 0, k) cout << " i = " << i << " dp1=" << dp[v][i] << " dp2=" << dp2[v][i] << endl;
}
int sub3 () {
FOR(i, 1, n) FOR(j, 0, k) dp[i][j] = dp2[i][j] = -1;
dfs2(1, -1);
return ans2;
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N;
k = K;
FOR(i, 0, n-2) {
int u = H[i][0], v = H[i][1], w = L[i];
u++;
v++;
adj[u].pb({v,w});
adj[v].pb({u,w});
}
if (N <= 1000)
return sub2();
else
return sub3();
}
/*
input 1
4 3
0 1 1
1 2 2
1 3 4
2
input 2
3 3
0 1 1
1 2 1
-1
input 3
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
2
*/
