#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;
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});
}
void trav (int v) {
//reach.clear();
c = -1;
calcSizes (v);
findCentroid (v, sz[v]);
minLen.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;
for (auto p : paths) {
int dep = p.f;
ll len = p.s;
//cout << " path dep = " << dep << " len = " << len << endl;
if (len > k) continue;
else if (len == k) {
if (ans == -1) ans = dep;
else ans = min(ans, dep);
} else {
int remLen = k - len;
if (minLen[remLen] > 0) {
int dep2 = minLen[remLen] + dep;
if (ans == -1) ans = dep2;
else ans = min(ans, dep2);
}
}
}
for (auto p : paths) {
int dep = p.f;
ll len = p.s;
if (len >= k) continue;
else {
if (minLen[dep] == 0) minLen[dep] = len;
else minLen[dep] = min(minLen[dep], (int)len);
}
}
}
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});
}
trav (1);
return ans;
}
/*
2 2
0 1 1
-1
*/
