#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n"
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define M 200005
vector<pii> adj[M];
int sz[M], dep[M], dist[M], vis[M], mini[1000006];
int k, n, ans = M;
void dfs(int node, int root){
sz[node] = 1;
//cout<<node<<endl;
for (auto i : adj[node]){
if (i.st == root || vis[i.st]) continue;
dfs(i.st, node);
sz[node] += sz[i.st];
}
}
void dfs2(int node, int root, int d, int dd, vector<pii> &all){
all.pb({dd, d});
for (auto i : adj[node]){
if (i.st == root || vis[i.st]) continue;
dfs2(i.st, node, d + 1, dd + i.nd, all);
}
}
int find_centroid(int node, int root, int S){
for (auto i : adj[node]){
if (i.st == root || vis[i.st]) continue;
if (sz[i.st] >= S / 2) return find_centroid(i.st, node, S);
}
return node;
}
void f(int node){
dfs(node, 0);
node = find_centroid(node, 0, sz[node]);
vector<pii> v;
for (auto i : adj[node]){
if (vis[i.st]) continue;
vector<pii> tmp;
dfs2(i.st, node, 1, i.nd, tmp);
for (auto j : tmp){
if (j.st <= k) ans = min(ans, mini[k - j.st] + j.nd);
}
for (auto j : tmp){
if (j.st <= k) mini[j.st] = min(mini[j.st], j.nd);
}
for (auto j : tmp)
{
v.pb(j);
}
}
for (auto i : v){
if (i.st <= k) mini[i.st] = M;
}
vis[node] = 1;
for (auto i : adj[node]){
if (vis[i.st] == 0) f(i.st);
}
}
int best_path(int N, int K, int H[][2], int L[]){
k = K, n = N;
for (int i = 0; i < N - 1; i++){
int u = H[i][0] + 1, v = H[i][1] + 1;
//cout<<u<<sp<<v<<endl;
adj[u].pb({v, L[i]});
adj[v].pb({u, L[i]});
}
for (int i = 1; i <= K; i++) mini[i] = M;
f(1);
if (ans < M)
return ans;
return -1;
}
