#define taskname ""
#include <bits/stdc++.h>
using namespace std;
const int kMaxN = 200005;
const int kMaxK = 1000005;
int n, k, min_length = kMaxN, sz[kMaxN], a[kMaxK];
bool deleted[kMaxN];
vector<pair<int, int>> adj[kMaxN];
int DFS1(int u, int p) {
sz[u] = 1;
for (auto i : adj[u]) {
int v = i.first;
if (v == p || deleted[v]) {
continue;
}
sz[u] += DFS1(v, u);
}
return sz[u];
}
int FindCentroid(int u, int p, int m) {
for (auto i : adj[u]) {
int v = i.first;
if (v == p || deleted[v]) {
continue;
}
if (sz[v] > m / 2) {
return FindCentroid(v, u, m);
}
}
return u;
}
void DFS2(int u, int p, int length, int total_weight, vector<pair<int, int>>& S) {
if (total_weight > k) {
return ;
}
S.push_back({length, total_weight});
for (auto i : adj[u]) {
int v = i.first, w = i.second;
if (v == p || deleted[v]) {
continue;
}
DFS2(v, u, length + 1, total_weight + w, S);
}
}
void CentroidDecomposition(int u) {
int x = DFS1(u, -1), y = FindCentroid(u, -1, x);
deleted[y] = true;
vector<int> U;
for (auto i : adj[y]) {
int z = i.first, t = i.second;
if (deleted[z]) {
continue;
}
vector<pair<int, int>> S;
DFS2(z, y, 1, t, S);
for (auto j : S) {
if (a[k - j.second] == -1) {
continue;
}
if (j.first + a[k - j.second] < min_length) {
min_length = j.first + a[k - j.second];
}
}
for (auto j : S) {
if (j.second > 0) {
U.push_back(j.second);
}
if (a[j.second] == -1 || a[j.second] > j.first) {
a[j.second] = j.first;
}
}
}
for (int i : U) {
a[i] = -1;
}
for (auto i : adj[y]) {
int z = i.first;
if (!deleted[z]) {
CentroidDecomposition(z);
}
}
}
int best_path(int N, int K, int H[][2], int L[]) {
k = K;
for (int i = 0; i < N; i++) {
adj[H[i][0]].push_back(make_pair(H[i][1], L[i]));
adj[H[i][1]].push_back(make_pair(H[i][0], L[i]));
}
a[0] = 0;
for (int i = 1; i <= k; i++) {
a[i] = -1;
}
int root = 0;
CentroidDecomposition(root);
return (min_length == kMaxN ? -1 : min_length);
}
