#include<algorithm>
#include<iostream>
#include<cstring>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<map>
#include<set>
using namespace std;
#define ll long long
struct centroid_tree{
vector<vector<pair<int, int>>> adj;
vector<bool> vis;
vector<int> par, sz;
vector<ll> cnt;
map<int, int> paths;
int N, K, answer;
void init(int _N, int len){
int N = _N; K = len;
adj = vector<vector<pair<int, int>>>(N+2, vector<pair<int, int>>());
vis = vector<bool>(N+2);
par = vector<int>(N+2);
sz = vector<int>(N+2);
answer = 1e9;
}
void edge(int u, int v, int w){
adj[u].push_back(make_pair(v, w));
adj[v].push_back(make_pair(u, w));
}
int get_size(int cur, int p = -1){
sz[cur] = 1;
for(pair<int, int> ch : adj[cur]){
if(ch.first != p && !vis[ch.first]){
sz[cur] += get_size(ch.first, cur);
}
}
return sz[cur];
}
int find_centroid(int cur, int p, int total){
for(pair<int, int> ch : adj[cur]){
if(sz[ch.first] > total/2 && ch.first != p && !vis[ch.first]){
return find_centroid(ch.first, cur, total);
}
}
return cur;
}
void calc(int cur, int p, int depth, int step, int flag){
if(depth > K)return;
if(flag){
if(!paths.count(depth)){
paths[depth] = step;
}
else{
paths[depth] = min(paths[depth], step);
}
}
else{
if(paths.count(K - depth)){
answer = min(answer, step + paths[K - depth]);
}
}
for(pair<int, int> ch : adj[cur]){
if(ch.first != p && !vis[ch.first]){
calc(ch.first, cur, depth + ch.second, step + 1, flag);
}
}
}
void build(int cur = 1, int p = -1){
get_size(cur);
int cen = find_centroid(cur, p, sz[cur]);
vis[cen] = 1;
par[cen] = p;
paths[0] = 0;
for(pair<int, int> ch : adj[cen]){
if(!vis[ch.first]){
calc(ch.first, cen, ch.second, 1, 0);
calc(ch.first, cen, ch.second, 1, 1);
}
}
paths.clear();
for(pair<int, int> ch : adj[cen]){
if(!vis[ch.first]){
build(ch.first, cen);
}
}
}
};
centroid_tree CT;
int best_path(int N, int K, int H[][2], int L[]){
CT.init(N, K);
for(int i = 0; i < N-1; ++i){
int u = H[i][0] + 1, v = H[i][1] + 1;
CT.edge(u, v, L[i]);
}
CT.build();
int answer = CT.answer;
return (answer == 1e9 ? -1 : answer);
}
