#include <bits/stdc++.h>
#include "race.h"
typedef long double ld;
typedef long long ll;
using namespace std;
int di[] = {1, 0, -1, 0};
int dj[] = {0, 1, 0, -1};
const ll oo = 1e18, MOD = 1e9 + 7;
const int N = 1e6 + 5, M = 1e6 + 5;
const ld PI = acos(-1.0), EPS = 1e-9;
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
int t, n, m, k, a[N], sz[N], tmp[N], mx, l[N], r[N];
vector<pair<int, int>> v[N];
bool vis[N];
int ans = 1e9;
int get_subtree_sizes(int node, int p = -1) {
sz[node] = 1;
for (auto x:v[node]) if (x.first != p && !vis[x.first]) sz[node] += get_subtree_sizes(x.first, node);
return sz[node];
}
int get_centroid(int node, int size, int p = -1) {
for (auto x:v[node]) {
if (x.first == p || vis[x.first]) continue;
if (sz[x.first] >= size) return get_centroid(x.first, size, node);
}
return node;
}
bool y;
void get_cnt(int node, int p, int yes, int sum, int level) {
if (sum > k) return;
if (sum == k) ans = min(ans, level);
if (yes == 1) tmp[sum] = min(tmp[sum], level);
else if (yes) tmp[sum] = 1e9;
else ans = min(ans, level + tmp[k - sum]);
for (auto x:v[node]) if (x.first != p && !vis[x.first]) get_cnt(x.first, node, yes, sum + x.second, level + 1);
}
void centroid_decomp(int node = 0) {
get_subtree_sizes(node);
int c = get_centroid(node, sz[node] / 2);
vis[c] = 1;
if (c == 6) y = 1;
else y = 0;
mx = 0;
for (auto x:v[c]) if (!vis[x.first]) get_cnt(x.first, c, 0, x.second, 1), get_cnt(x.first, c, 1, x.second, 1);
for (auto x:v[c]) if (!vis[x.first]) get_cnt(x.first, c, 2, x.second, 1);
for (auto x:v[c]) if (!vis[x.first]) centroid_decomp(x.first);
}
//#define endl '\n'
int best_path(int N, int K, int H[][2], int L[]) {
//ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//freopen("marsllino.in", "r", stdin);
//memset(dp, -1, sizeof dp);
fill(tmp, tmp + 1000000 + 5, 1e9);
n = N, k = K;
for (int i = 1; i < n; i++) {
v[H[i][1]].push_back({H[i][0], L[i]});
v[H[i][0]].push_back({H[i][1], L[i]});
}
centroid_decomp();
cout << (ans == 1e9 ? -1 : ans);
return 0;
}
