#include "race.h"
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define all(x) (x).begin(),(x).end()
#define pb push_back
const int mxN = 200000;
const int ninf = -1e9;
struct comp {
bool operator() (const array<int, 2>& a, const array<int, 2>& b) const {
return a[0] == b[0] ? a[1] < b[1] : a[0] < b[0];
}
};
int k;
vector<array<int, 2>> adj[mxN];
set<array<int, 2>, comp> paths[mxN];
array<int, 2> add[mxN];
int ans = 1e9;
void dfs(int v, int p) {
for(auto[i, w] : adj[v]) {
if(i == p) continue;
dfs(i, v);
add[i][0] += w;
++add[i][1];
if(paths[i].size() > paths[v].size()) {
swap(add[i], add[v]);
paths[v].swap(paths[i]);
}
for(auto[len, edges] : paths[i]) {
int cur = len + add[i][0];
array<int, 2> search = {k - cur - add[v][0], ninf};
auto lb = paths[v].lower_bound(search);
if(lb != paths[v].end() && (*lb)[0] + add[v][0] + cur == k) {
ans = min(ans, edges + add[i][1] + (*lb)[1] + add[v][1]);
}
paths[v].insert({len + add[i][0] - add[v][0], edges + add[i][1] - add[v][1]});
}
paths[i].clear();
}
array<int, 2> find = {k - add[v][0], ninf};
auto lb = paths[v].lower_bound(find);
if(lb != paths[v].end() && (*lb)[0] + add[v][0] == k) {
ans = min(ans, (*lb)[1] + add[v][1]);
}
paths[v].insert({-add[v][0], -add[v][1]});
}
int best_path(int N, int K, int H[][2], int L[]) {
k = K;
for(int i = 0; i < N - 1; ++i) {
adj[H[i][0]].pb({H[i][1], L[i]});
adj[H[i][1]].pb({H[i][0], L[i]});
}
dfs(0, -1);
return ans == 1e9 ? -1 : ans;
}
/*
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int N, K; cin >> N >> K;
int H[N - 1][2], L[N - 1];
for(int i = 0; i < N - 1; ++i) {
cin >> H[i][0] >> H[i][1] >> L[i];
}
cout << best_path(N, K, H, L) << "\n";
}
*/
