//بسم الله الرحمان الرحيم
//we are the winners
//we are the champions
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pb emplace_back
#define lv (v<<1)
#define rv ((v<<1)|1)
#define endl '\n'
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
template<int M>
struct Cyclic {
int val = 0;
Cyclic() = default;
Cyclic(int _val) : val(_val) {}
Cyclic(ll _val) : val((int)_val) {}
Cyclic(const Cyclic& other) : val(other.val) {}
Cyclic operator+(const Cyclic& other) const {
return Cyclic((val + other.val) % M);
}
Cyclic operator-(const Cyclic& other) const {
return Cyclic((val - other.val + M) % M);
}
Cyclic operator*(const Cyclic& other) const {
return Cyclic(1LL * val * other.val % M);
}
Cyclic operator/(const Cyclic& other) const {
return (*this) * other.inv();
}
Cyclic& operator+=(const Cyclic& other) {
val = (val + other.val) % M;
return (*this);
}
Cyclic& operator-=(const Cyclic& other) {
val = (val - other.val + M) % M;
return (*this);
}
Cyclic& operator*=(const Cyclic& other) {
val = 1LL * val * other.val % M;
return (*this);
}
Cyclic& operator/=(const Cyclic& other) {
(*this) = (*this) / other;
return (*this);
}
Cyclic pow(ll p) const {
Cyclic res(1), base(val);
while (p > 0) {
if (p & 1) res *= base;
base *= base;
p >>= 1;
}
return res;
}
Cyclic inv() const {
assert(val != 0);
return pow(M-2);
}
static Cyclic pow(ll a, ll p) {
return Cyclic(a).pow(p);
}
friend istream& operator>>(istream& is, Cyclic& c) {
is >> c.val;
return is;
}
friend ostream& operator<<(ostream& os, const Cyclic& c) { return os << c.val; }
};
constexpr int MOD = 998244353;
typedef Cyclic<MOD> cint;
constexpr int MAXN = 2e5 + 5, MAXK = 1e6+5;
int sub_sz[MAXN], is_centroid[MAXN], other[MAXK], n, k, ans;
struct Centroid_Decomposition {
/* Internals */
const vector<vector<pii>>& adj;
/* Problem Specific */
// ...
/* Initialize the Centroid Decomposition */
Centroid_Decomposition(const vector<vector<pii>> &g) : adj(g) {}
/* Update subtree size of each node */
int updateSize(int u, int p = -1){
sub_sz[u] = 1;
for (auto [v, w] : adj[u])
if (v != p && !is_centroid[v])
sub_sz[u] += updateSize(v, u);
return sub_sz[u];
}
/* Get centroid of subtree rooted at u */
int getCentroid(int u, int target, int p = -1){
for(auto [v, w] : adj[u]){
if(v == p || is_centroid[v]) continue;
if((sub_sz[v]<<1) > target)
return getCentroid(v, target, u);
}
return u;
}
void update_ans(int u, int p, int dep_cent, int dist_cent) {
if (dist_cent > k) return;
int cand = other[k-dist_cent];
if (cand > 0 || k-dist_cent == 0) ans = min(ans, cand + dep_cent);
for (auto& [nxt, w] : adj[u]) {
if(nxt == p || is_centroid[nxt]) continue;
update_ans(nxt, u, dep_cent+1, dist_cent+w);
}
}
void update_lens(int u, int p, int dep_cent, int dist_cent, vi& to_rem) {
if (dist_cent > k) return;
int& cand = other[dist_cent];
if (cand > 0) cand = min(cand, dep_cent);
else {
to_rem.pb(dist_cent);
cand = dep_cent;
}
for (auto& [nxt, w] : adj[u]) {
if(nxt == p || is_centroid[nxt]) continue;
update_lens(nxt, u, dep_cent+1, dist_cent+w, to_rem);
}
}
/* Decompose tree into centroid tree */
void Centroid(int u, int p){
int cur_sz = updateSize(u);
int centroidPoint = getCentroid(u, cur_sz);
is_centroid[centroidPoint] = true;
vi to_rem;
to_rem.reserve(cur_sz);
// do something with centroid
for(auto [v, w] : adj[centroidPoint]){
if(is_centroid[v]) continue;
update_ans(v, centroidPoint, 1, w);
update_lens(v, centroidPoint, 1, w, to_rem);
}
for (int x : to_rem) other[x] = 0;
for(auto [v, w] : adj[centroidPoint]){
if(is_centroid[v]) continue;
// prepare for a dive
Centroid(v, centroidPoint);
// recover
}
// do something with centroid
}
// Call this function to decompose the tree
void Decompose(){ Centroid(0, -1); }
};
int best_path(int _n, int _k, int e[][2], int w[]) {
n = _n; k = _k;
ans = n;
vector<vector<pii>> adj(n);
rep(i, 0, n-1) {
adj[e[i][0]].pb(e[i][1], w[i]);
adj[e[i][1]].pb(e[i][0], w[i]);
}
Centroid_Decomposition cent(adj);
cent.Decompose();
if (ans == n) return -1;
return ans;
}
