#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <deque>
#include <queue>
#include <tuple>
#include <cmath>
#include <cctype>
#include <stack>
#include <cassert>
#include <iomanip>
#include <complex>
using namespace std;
using ll = long long;
vector<pair<int, int>> adj[200000];
int subs[200000];
bool rm[200000];
int ans;
map<int, int> mh; // minimum number of highways to construct path of length idx
vector<pair<int, int>> cand;
int rsubs(int v, int p) {
subs[v] = 1;
for (auto u : adj[v])
if (u.first != p && !rm[u.first]) subs[v] += rsubs(u.first, v);
return subs[v];
}
int find_centroid(int v, int p, int sz) {
for (auto u : adj[v])
if (u.first != p && !rm[u.first] && subs[u.first] > sz/2) return find_centroid(u.first, v, sz);
return v;
}
void dfs(int v, int p, int len, int d) {
cand.push_back({len, d});
for (auto u : adj[v])
if (u.first != p && !rm[u.first]) dfs(u.first, v, len+u.second, d+1);
}
void build(int v, int K) {
rsubs(v, -1);
v = find_centroid(v, -1, subs[v]);
// consider all paths passing through node v
mh[0] = 0;
for (auto u: adj[v]) {
if (rm[u.first]) continue;
dfs(u.first, v, u.second, 1);
for (auto pp : cand) {
int len = pp.first, d = pp.second;
if (mh.find(K-len) != mh.end()) ans = min(ans, mh[K-len]+d);
}
for (auto pp : cand) {
if (mh.find(pp.first) == mh.end()) mh[pp.first] = pp.second;
else mh[pp.first] = min(mh[pp.first], pp.second);
}
cand.clear();
}
mh.clear();
rm[v] = true;
for (auto u : adj[v]) {
if (rm[u.first]) continue;
build(u.first, K);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
for (int i = 0; i < N; i++) {
adj[i].clear();
rm[i] = false;
}
for (int i = 0; i < N-1; i++) {
adj[H[i][0]].push_back({H[i][1], L[i]});
adj[H[i][1]].push_back({H[i][0], L[i]});
}
ans = 1e9;
build(1, K);
return ans==1e9 ? -1 : ans;
}
/*int main() {
//int N = 4, K = 3;
//int H[][2] = {{0, 1}, {1, 2}, {1, 3}};
//int L[] = {1, 2, 4};
//cout << best_path(N, K, H, L) << endl;
//int N = 3, K = 3;
//int H[][2] = {{0, 1}, {1, 2}};
//int L[] = {1, 1};
//cout << best_path(N, K, H, L) << endl;
int N = 11, K = 12;
int H[][2] = {{0, 1}, {0, 2}, {2, 3}, {3, 4}, {4, 5}, {0, 6}, {6, 7}, {6, 8}, {8, 9}, {8, 10}};
int L[] = {3, 4, 5, 4, 6, 3, 2, 5, 6, 7};
cout << best_path(N, K, H, L) << endl;
}*/
