#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int N, K;
vector<vector<pair<int,int>>> adj; // (vizinho, peso)
vector<int> sz;
vector<char> removed;
int ans = INF;
int calc_sz(int v, int p){
sz[v] = 1;
for(auto &e : adj[v]){
int u = e.first;
if(u == p || removed[u]) continue;
sz[v] += calc_sz(u, v);
}
return sz[v];
}
int find_centroid(int v, int p, int n){
for(auto &e : adj[v]){
int u = e.first;
if(u == p || removed[u]) continue;
if(sz[u] > n/2) return find_centroid(u, v, n);
}
return v;
}
// coleta (peso_total, dist_em_arestas) de todos os nós na subárvore de v,
// começando com dist = startDist, weight = startW
void collect_paths(int v, int p, int dist, int weight, vector<pair<int,int>> &out){
if(weight > K) return; // otimização: não precisamos de pesos > K
out.emplace_back(weight, dist);
for(auto &e : adj[v]){
int u = e.first, w = e.second;
if(u == p || removed[u]) continue;
collect_paths(u, v, dist+1, weight + w, out);
}
}
void decompose(int entry){
int n = calc_sz(entry, -1);
int centroid = find_centroid(entry, -1, n);
// mark centroid
removed[centroid] = 1;
// best: mapa peso -> menor distancia para caminhos já processados (vindo de filhos anteriores)
unordered_map<int,int> best;
best.reserve(64);
best[0] = 0; // ficar no centróide: peso 0, dist 0
for(auto &e : adj[centroid]){
int u = e.first, w = e.second;
if(removed[u]) continue;
vector<pair<int,int>> paths;
collect_paths(u, centroid, 1, w, paths);
// primeiro, para cada caminho deste filho, tenta combinar com best (filhos anteriores)
for(auto &p : paths){
int pw = p.first;
int pd = p.second;
int need = K - pw;
auto it = best.find(need);
if(it != best.end()){
ans = min(ans, pd + it->second);
}
}
// depois atualiza best com os caminhos deste filho
for(auto &p : paths){
int pw = p.first;
int pd = p.second;
auto it = best.find(pw);
if(it == best.end() || pd < it->second) best[pw] = pd;
}
}
// recursão nos componentes resultantes
for(auto &e : adj[centroid]){
int u = e.first;
if(!removed[u]) decompose(u);
}
// opcional: removed[centroid] = 0; // se quisermos reutilizar (mas não é necessário)
}
int best_path(int NN, int KK, int H[][2], int L[]){
N = NN; K = KK;
adj.assign(N, {});
for(int i=0;i<N-1;i++){
int u = H[i][0], v = H[i][1], w = L[i];
adj[u].push_back({v,w});
adj[v].push_back({u,w});
}
sz.assign(N,0);
removed.assign(N,0);
ans = INF;
decompose(0);
if(ans == INF) return -1;
return ans;
}
