#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef long long ll;
const int MAXN = 1000100;
int n, k;
vii adj[MAXN];
int ans = -1;
bool vis[MAXN];
int sz[MAXN];
//vi reach;
int c = -1;
//vector<pair<int, ll>> paths;
//unordered_map<int, int> minLen;
int minLen[MAXN];
vi changed;
void calcSizes (int v, int p = -1) {
sz[v] = 1;
//reach.pb(v);
for (auto pp : adj[v]) {
int u = pp.f;
// ll w = pp.s;
if (u == p) continue;
if (vis[u]) continue;
calcSizes(u, v);
sz[v] += sz[u];
}
}
void findCentroid (int v, int allSz, int p = -1) {
bool can = true;
for (auto pp : adj[v]) {
int u = pp.f;
//ll w = pp.s;
if (u == p) continue;
if (vis[u]) continue;
findCentroid(u, allSz, v);
if (sz[u] > allSz/2) can = false;
}
if ((allSz - sz[v]) > allSz/2) can = false;
if (can) c = v;
}
void getPaths (int v, ll len, int dep, int p = -1) {
for (auto pp : adj[v]) {
int u = pp.f;
ll w = pp.s;
if (u == p) continue;
if (vis[u]) continue;
getPaths(u, len+w, dep+1, v);
}
//paths.pb({dep, len});
if (len <= k) {
int remLen = k - len;
if (minLen[remLen] != -1) {
int dep2 = minLen[remLen] + dep;
if (ans == -1) ans = dep2;
else ans = min(ans, dep2);
}
}
}
void getPaths2 (int v, ll len, int dep, int p = -1) {
for (auto pp : adj[v]) {
int u = pp.f;
ll w = pp.s;
if (u == p) continue;
if (vis[u]) continue;
getPaths2(u, len+w, dep+1, v);
}
//paths.pb({dep, len});
if (len < k) {
if (minLen[len] == -1) minLen[len] = dep;
else minLen[len] = min(minLen[len], dep);
changed.pb(len);
}
}
void trav (int v) {
//reach.clear();
c = -1;
calcSizes (v);
findCentroid (v, sz[v]);
//minLen.clear();
//FOR(i, 0, k) minLen[i] = -1;
minLen[0] = 0;
changed.clear();
for (auto pp : adj[c]) {
int u = pp.f;
ll w = pp.s;
if (vis[u]) continue;
//paths.clear();
getPaths(u, w, 1, c);
//cout << " paths from v = " << v << " trrough u = " << u << endl;
getPaths2(u,w,1,c);
}
for (int x : changed)
minLen[x] = -1;
vis[c] = true;
for (auto pp : adj[c]) {
int u = pp.f;
// ll w = pp.s;
if (vis[u]) continue;
trav(u);
}
}
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});
}
FOR(i, 1, k) minLen[i] = -1;
trav (1);
return ans;
}
/*
2 2
0 1 1
-1
*/
