#line 1 "paper.cpp"
#include <bits/stdc++.h>
#line 3 "library2/utility/infty.hpp"
template <typename T, T Div = 2> constexpr T infty = std::numeric_limits<T>::max() / Div;
#line 3 "library2/utility/len.hpp"
template <class Container> int len(const Container&c){
return static_cast<int>(std::size(c));
}
#line 2 "library2/utility/rec_lambda.hpp"
template <class F> class RecursiveLambda {
F f;
public:
explicit constexpr RecursiveLambda(F &&f_) : f(std::forward<F>(f_)) {}
template <class... Args> constexpr auto operator()(Args &&...args) const {
return f(*this, std::forward<Args>(args)...);
}
};
template <class F> constexpr decltype(auto) rec_lambda(F &&f) {
return RecursiveLambda<F>(std::forward<F>(f));
}
#line 3 "library2/utility/rep.hpp"
class Range {
struct Iterator {
int itr;
constexpr Iterator(const int pos) noexcept : itr(pos) {}
constexpr void operator++() noexcept {
++itr;
}
constexpr bool operator!=(const Iterator &other) const noexcept {
return itr != other.itr;
}
constexpr int operator*() const noexcept {
return itr;
}
};
const Iterator first, last;
public:
explicit constexpr Range(const int f, const int l) noexcept
: first(f), last(std::max(f, l)) {}
constexpr Iterator begin() const noexcept {
return first;
}
constexpr Iterator end() const noexcept {
return last;
}
};
constexpr Range rep(const int l, const int r) noexcept {
return Range(l, r);
}
constexpr Range rep(const int n) noexcept {
return Range(0, n);
}
#line 2 "library2/utility/setmax.hpp"
template <typename T> bool setmax(T &lhs, const T &rhs) {
if (lhs < rhs) {
lhs = rhs;
return true;
}
return false;
}
#line 2 "library2/utility/setmin.hpp"
template <typename T> bool setmin(T& lhs, const T& rhs) {
if (lhs > rhs) {
lhs = rhs;
return true;
}
return false;
}
#line 9 "paper.cpp"
#include "race.h"
int N;
int K;
struct Edge {
int to;
int cost;
};
std::vector<std::vector<Edge>> Tree;
struct DpData {
std::map<int, int> d;
int adj;
int depth;
// real key : d.key + adj
// real value : depth - d.value
int size() const {
return len(d);
}
};
void merge(DpData &a, DpData &b) {
assert(a.size() >= b.size());
for (const auto &[key, value] : b.d) {
const int r = key + b.adj - a.adj;
if (a.d.find(r) == a.d.end()) {
a.d[r] = a.depth - (b.depth - value);
} else {
setmax(a.d[r], a.depth - (b.depth - value));
}
}
}
int calc_dp() {
int answer = infty<int>;
auto dfs = rec_lambda([&](auto &&f, const int v, const int p) -> DpData {
if (v != 0 and len(Tree[v]) == 1) {
DpData ret;
ret.adj = 0;
ret.depth = 0;
ret.d[0] = 0;
return ret;
}
const int c = len(Tree[v]);
std::vector<DpData> children(c);
auto collect = [&]() {
int count = 0;
for (const auto [to, cost] : Tree[v]) {
if (to == p) {
children[count].adj = -1;
} else {
children[count] = f(to, v);
children[count].adj += cost;
++children[count].depth;
}
++count;
}
int base = (int)(std::max_element(children.begin(), children.end(),
[](const DpData &a, const DpData &b) {
return a.size() < b.size();
}) -
children.begin());
return base;
};
int base = collect();
for (const int i : rep(c)) {
if (i == base) {
continue;
}
if (children[i].adj == -1) {
continue;
}
for (const auto &[key, value] : children[i].d) {
const int r = K - (key + children[i].adj + children[base].adj);
if (children[base].d.find(r) != children[base].d.end()) {
setmin(answer, (children[i].depth - value) +
(children[base].depth - children[base].d[r]));
}
}
merge(children[base], children[i]);
}
children[base].d[-children[base].adj] = children[base].depth;
const int r = K - children[base].adj;
if (children[base].d.find(r) != children[base].d.end()) {
setmin(answer, children[base].depth - children[base].d[r]);
}
return std::move(children[base]);
});
dfs(0, N);
return answer == infty<int> ? -1 : answer;
}
int best_path(int n, int k, int H[][2], int L[]) {
N = n;
K = k;
Tree.resize(N);
for (const int i : rep(N - 1)) {
Tree[H[i][0]].push_back({H[i][1], L[i]});
Tree[H[i][1]].push_back({H[i][0], L[i]});
}
return calc_dp();
}
/*
int main() {
int n, k;
std::cin >> n >> k;
int H[20][2];
int L[20];
for (const int i : rep(n - 1)) {
int a, b, l;
std::cin >> a >> b >> l;
H[i][0] = a, H[i][1] = b;
L[i] = l;
}
std::cout << best_path(n, k, H, L) << std::endl;
}
*/
