#include <bits/stdc++.h>
using namespace std;
const int inf = (int) 1e9;
const int N = (int) 2e5 + 1;
const int M = (int) 1e6 + 1;
vector<pair<int, int>> adj[N];
vector<pair<int, int>> tmp;
int Get_Min[M], idx[M];
int sz[N];
bool vis[N];
int ans = inf;
int k;
int Dfs2(int node, int pre, int depth, int tot, int id) {
if (tot > k) return inf;
int res = inf;
if (idx[k - tot] == id) {
res = min(res, Get_Min[k - tot] + depth);
}
tmp.emplace_back(tot, depth);
for (auto [x, y] : adj[node]) {
if (x == pre || vis[x]) {
continue;
}
res = min(res, Dfs2(x, node, depth + 1, tot + y, id));
}
return res;
}
int best_path(int n, int K, int edges[][2], int w[]) {
k = K;
for (int i = 0; i < n - 1; i++) {
int a = edges[i][0];
int b = edges[i][1];
int c = w[i];
adj[a].emplace_back(b, c);
adj[b].emplace_back(a, c);
}
int cnt = 0;
for (int i = 0; i <= k; i++) {
Get_Min[i] = inf;
idx[i] = -1;
}
function<int(int, int)> Get_Sub_Sizes = [&](int node, int pre) {
sz[node] = 1;
for (auto [x, y] : adj[node]) {
if (x == pre || vis[x]) {
continue;
}
sz[node] += Get_Sub_Sizes(x, node);
}
return sz[node];
};
function<int(int, int, int)> Get_Centroid = [&](int node, int pre, int s) {
for (auto [x, y] : adj[node]) {
if (x == pre || vis[x]) {
continue;
}
if (sz[x] > s / 2) {
return Get_Centroid(x, node, s);
}
}
return node;
};
function<void(int, int)> Decompose = [&](int node, int pre) {
Get_Sub_Sizes(node, pre);
int c = Get_Centroid(node, pre, sz[node]);
vis[c] = true;
Get_Min[0] = 0;
idx[0] = cnt++;
for (auto [x, y] : adj[c]) {
if (x == pre || vis[x]) continue;
tmp.clear();
ans = min(ans, Dfs2(x, c, 1, y, idx[0]));
for (int j = 0; j < (int) tmp.size(); j++) {
if (idx[tmp[j].first] == idx[0]) {
Get_Min[tmp[j].first] = min(Get_Min[tmp[j].first], tmp[j].second);
}
else {
Get_Min[tmp[j].first] = tmp[j].second;
idx[tmp[j].first] = idx[0];
}
}
}
for (auto [x, y] : adj[c]) {
if (vis[x]) {
continue;
}
Decompose(x, c);
}
};
Decompose(0, -1);
if (ans >= inf) {
return -1;
}
return ans;
}
