#include<bits/stdc++.h>
using namespace std;


int best_path(int N, int K, int H[][2], int L[]) {
	const int INF = 1e9;
	int ans = INF;

	vector<vector<pair<int, int>>> adj(N);
	for (int i = 0; i+1 < N; ++i) {
		// cout << H[i][0] << ' ' << H[i][1] << endl;
		adj[H[i][0]].push_back({H[i][1], L[i]});
		adj[H[i][1]].push_back({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, int64_t depth, int level, auto& path) -> void {
		if (depth > K) 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) {
				if (dist > K) continue;
				ans = min(ans, vals[K - dist] + level);
				if (vals[K - dist] == INF && dist == K) {
					ans = min(ans, level);
				}
			}

			for (auto [dist, level] : path) {
				if (dist > K) continue;
				vals[dist] = min(vals[dist], level);
			}
		}
		for (auto [nxt, weight] : adj[cur]) {
			if (deleted[nxt]) continue;
			self(self, nxt);
		}
	};

	rec(rec, 0);

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