#pragma gcc optimize("ofast")
#pragma gcc optimization ("unroll-loops")
#include<bits/stdc++.h>
using namespace std;


int best_path(int n, int k, int h[][2], int l[]) {
	mt19937 rng(47);
	const int inf = 1e9;
	int ans = inf;

	vector<int> perm(n); iota(perm.begin(), perm.end(), 0);
	shuffle(perm.begin(), perm.end(), rng);

	vector<vector<pair<int, int>>> adj(n);
	for (int i = 0; i+1 < n; ++i) {
		// cout << h[i][0] << ' ' << h[i][1] << endl;
		adj[perm[h[i][0]]].push_back({perm[h[i][1]], l[i]});
		adj[perm[h[i][1]]].push_back({perm[h[i][0]], l[i]});
	}

	vector<bool> deleted(n);
	vector<pair<int, int>> max_sub(n);
	auto dfs = [&](auto&& self, int cur, int prv) -> int {
		int sz = 1;
		max_sub[cur] = {0, -1};
		for (auto [nxt, weight] : adj[cur]) {
			if (nxt == prv || deleted[nxt]) continue;
			int cur_sz = self(self, nxt, cur);
			sz += cur_sz;
			max_sub[cur] = max(max_sub[cur], {cur_sz, nxt});
		}
		return sz;
	};

	auto get_dist = [&](auto& self, int cur, int prv, int depth, int level, auto& path) -> void {
		if (depth > k || level >= ans) return;
		path.push_back({depth, level});
		for (auto [nxt, weight] : adj[cur]) {
			if (nxt == prv || deleted[nxt]) continue;
			self(self, nxt, cur, depth + weight, level + 1, path);
		}
	};

	/*
	auto rec = [&](auto&& self, int cur) -> void {
		int total_sz = dfs(dfs, cur, -1);
		while (max_sub[cur].first * 2 > total_sz) cur = max_sub[cur].second;

		deleted[cur] = true;

		vector<int> vals(k + 1, inf);
		for (auto [nxt, weight] : adj[cur]) {
			if (deleted[nxt]) continue;

			vector<pair<int, int>> path; path.reserve(total_sz);
			get_dist(get_dist, nxt, cur, weight, 1, path);
	
			for (auto [dist, level] : path) {
				ans = min(ans, vals[k - dist] + level);
				if (vals[k - dist] == inf && dist == k) {
					ans = min(ans, level);
				}
			}

			for (auto [dist, level] : path) {
				vals[dist] = min(vals[dist], level);
			}
		}

		for (auto [nxt, weight] : adj[cur]) {
			if (deleted[nxt]) continue;
			self(self, nxt);
		}
	};

	rec(rec, 0);
	*/

	vector<int> bfs = {0};
	for (int z = 0; z < int(bfs.size()); ++z) {
		int cur = bfs[z];

		int total_sz = dfs(dfs, cur, -1);
		while (max_sub[cur].first * 2 > total_sz) cur = max_sub[cur].second;

		deleted[cur] = true;

		vector<int> vals(k + 1, inf);
		for (auto [nxt, weight] : adj[cur]) {
			if (deleted[nxt]) continue;

			vector<pair<int, int>> path; path.reserve(total_sz);
			get_dist(get_dist, nxt, cur, weight, 1, path);
	
			for (auto [dist, level] : path) {
				ans = min(ans, vals[k - dist] + level);
				if (vals[k - dist] == inf && dist == k) {
					ans = min(ans, level);
				}
			}

			for (auto [dist, level] : path) {
				vals[dist] = min(vals[dist], level);
			}
		}

		for (auto [nxt, weight] : adj[cur]) {
			if (deleted[nxt]) continue;
			bfs.push_back(nxt);
		}
	}

	return (ans == inf ? -1 : ans);
}