#include <bits/stdc++.h>
#include "race.h"
using namespace std;
const int MAX_N = 2e5 + 5;
const int MAX_K = 1e6 + 5;
int ans = 1e9;
vector<set<pair<int,int>>> g(MAX_N);
vector<int> sub(MAX_N);
int calc_sub(int node, int p) {
sub[node] = 1;
for (auto to : g[node]) {
if (to.first != p) {
sub[node] += calc_sub(to.first, node);
}
}
return sub[node];
}
int calc_centroid(int node, int p, int tam) {
for (auto to : g[node]) {
if (to.first != p && sub[to.first] > tam / 2) {
return calc_centroid(to.first, node, tam);
}
}
return node;
}
map<long long, int> best_way;
map<long long, int> add;
void dfs (int node, int p, long long l, int t) {
if (add.find(l) == add.end()) add[l] = t;
else add[l] = min (add[l], t);
for (auto to : g[node]) {
if (to.first != p) {
dfs (to.first, node, l + to.second, t + 1);
}
}
}
int _K;
void decompose(int node) {
best_way = map<long long, int> ();
best_way[0] = 0;
const int centroid = calc_centroid(node, -1, calc_sub(node, -1));
for (auto nxt : g[centroid]) {
g[nxt.first].erase({centroid, nxt.second});
add = map<long long, int> ();
dfs (nxt.first, -1, nxt.second, 1);
for (auto to : add) {
long long distancia = to.first;
int w = to.second;
long long need = _K - distancia;
if (need >= 0 && best_way.find(need) != best_way.end()) {
ans = min (ans, w + best_way[need]);
}
}
for (auto to : add) {
long long distancia = to.first;
int w = to.second;
if (best_way.find(distancia) == best_way.end()) best_way[distancia] = w;
else best_way[distancia] = min (best_way[distancia], w);
}
}
for (auto to : g[centroid]) {
decompose(to.first);
}
g[centroid].clear();
}
int best_path(int N, int K, int H[][2], int L[]) {
_K = K;
for (int i = 0; i < N - 1; i++) {
int st = H[i][0];
int et = H[i][1];
int w = L[i];
g[st].insert({et, w});
g[et].insert({st, w});
}
decompose(0);
return (ans > 1e8 ? -1 : ans);
}
