#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include "race.h"
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>
// #include <algo.hpp>
/*
Telebe of Adicto && Mamedov yani AzeTurk810
I see humans but no humanity
*/
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll = long long;
using namespace std;
#define ln '\n'
#define INFi 1e9
#define INFll 1e18
#ifdef ONPC
#include <algo.hpp>
#else
#define dbg(...)
#define dbg_out(...)
#endif
constexpr int up = 1e6 + 1;
int mp[up], last[up];
struct CentroiddeComposition {
int _n_, _k_, _ans_, _cur_;
vector<vector<pair<int, int>>> g;
vector<bool> removed;
vector<int> subSize, distFromCentroid, nodeFromCentroid;
vector<vector<int>> level;
CentroiddeComposition(int _n, vector<vector<pair<int, int>>> &_g, const int &_k) : g(_g), _n_(_n), _k_(_k), _ans_(INFi), _cur_(1) {
removed.assign(_n + 1, false);
distFromCentroid.assign(_n + 1, INFi);
nodeFromCentroid.assign(_n + 1, INFi);
subSize.resize(_n + 1);
level.resize(_n + 1);
}
int getSubSize(int v, int pa = -1) {
subSize[v] = 1;
for (const auto &[u, w] : g[v]) {
if (u == pa || removed[u])
continue;
getSubSize(u, v);
subSize[v] += subSize[u];
}
return subSize[v];
}
void getDistFromCentroid(int v, int pa) {
if (distFromCentroid[v] > _k_) // XXX: it can be in the same subtree
return;
// INFO: is it in other side of centroid???
if (distFromCentroid[v] <= _k_) {
int target = _k_ - distFromCentroid[v];
if (last[target] != _cur_) {
mp[target] = INFi;
last[target] = _cur_;
}
_ans_ = min(_ans_, mp[target] + nodeFromCentroid[v]);
}
for (const auto &[u, w] : g[v]) {
if (pa == u || removed[u])
continue;
distFromCentroid[u] = distFromCentroid[v] + w;
nodeFromCentroid[u] = nodeFromCentroid[v] + 1;
getDistFromCentroid(u, v);
}
}
void addDistFromCentoid(int v, int pa) {
if (distFromCentroid[v] > _k_) {
return;
}
if (last[distFromCentroid[v]] != _cur_) {
mp[distFromCentroid[v]] = INFi;
last[distFromCentroid[v]] = _cur_;
}
mp[distFromCentroid[v]] = min(mp[distFromCentroid[v]], nodeFromCentroid[v]);
for (const auto &[u, w] : g[v]) {
if (pa == u || removed[u])
continue;
addDistFromCentoid(u, v);
}
}
int findCentroid(int v, int half, int pa = -1) {
for (const auto &[u, w] : g[v]) {
if (u == pa || removed[u] || subSize[u] <= half) {
continue;
}
return findCentroid(u, half, v);
}
return v;
}
int solve(int centroid, int sizeoftree) { // INFO: Centroid ucun cavab
// WARNING: You must initilaze before getDistFromCentroid Manualy
// nodeFromCentroid[v] = 0;
// distFromCentroid[v] = 0;
// mp.clear();
// mp_same.clear();
// getDistFromCentroid(v, -1);
// mp.assign(_k_ + 1, INFi);// XXX: Can't assign
_cur_++;
last[0] = _cur_;
mp[0] = 0;
for (const auto &[u, w] : g[centroid]) {
nodeFromCentroid[u] = 1;
distFromCentroid[u] = w;
getDistFromCentroid(u, centroid);
addDistFromCentoid(u, centroid);
}
return _ans_;
}
int build(int v = 0, int id = 0) { // TODO: Inside
int centroid = findCentroid(v, getSubSize(v) >> 1);
removed[centroid] = true;
solve(centroid, subSize[v]);
for (const auto &[u, w] : g[centroid]) {
if (removed[u])
continue;
level[id + 1].push_back(build(u, id + 1)); // WARNING: should it be id + 1 or id ???
}
return centroid;
}
};
int best_path(int N, int K, int H[][2], int L[]) {
// return 0;
vector<vector<pair<int, int>>> g(N);
for (int i = 0; i < N - 1; i++) {
const int &u = H[i][0], &v = H[i][1], &w = L[i];
g[u].push_back(make_pair(v, w));
g[v].push_back(make_pair(u, w));
}
CentroiddeComposition t(N, g, K);
t.level[0].push_back(t.build(0));
if (t._ans_ == INFi)
t._ans_ = -1;
return t._ans_;
}
// Attack on titan<3
// Just Imaginary
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣀⠀⠀⠀⢀⣴⣾⠀⠀⠀⡀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣦⣾⣿⣿⣿⣿⣿⡆⠁⠀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣿⣿⣿⣿⣿⣿⣿⣿⡿⠁⠀⡠⠂⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠠⠔⠚⣿⣿⣿⣿⣿⣦⡄⠀⠁⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⠠⠐⢂⠉⡀⣀⣤⣄⢻⣿⣿⡟⢈⡹⣿⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⡀⠄⠂⠈⠀⣶⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠘⣷⡀⠀⡀⠐⠂⠐⢄
⠀⠀⠀⠀⠀⠀⠀⣿⣿⠟⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣀⣾⣷⠯⠀⠤⠤⠄⠈
⠀⠀⠀⠀⠀⠀⣼⣿⡟⠀⠀⣹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣰⣿⠋⠀⠀⢠⣾⣿⣿⣿⣿⣿⣭⠟⢻⣿⣿⣿⣿⡿⠁⠀⠀⠀⠀
⠀⠀⠀⣀⣶⡟⠁⠀⢾⣶⣿⠟⠉⠈⢻⣿⣿⣿⣦⣜⠀⠛⠛⠿⠁⠀⠀⠀⠀⠀
⠚⠻⠿⠿⡿⠁⠀⢠⣿⣿⠁⠀⣠⠖⠋⠉⠻⣿⣿⣿⣶⡀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⣰⣿⡿⠃⠠⠊⠁⠀⠀⠀⠀⠈⢿⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⣴⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⣠⣾⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⢀⣴⠾⠟⠛⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
*/
