#include <bits/stdc++.h>
#include "race.h"
using namespace std;
const int N = 2e5 + 5;
int n, k, ans = 1e9;
int depth[N], dist[N];
vector<pair<int, int>> adj[N];
set<pair<int, int>> S[N];
void dfs(int u = 1, int p = 0){
for (auto [v, w]: adj[u]){
if (v == p) continue;
dist[v] = dist[u] + w;
depth[v] = depth[u] + 1;
dfs(v, u);
}
}
void STL(int u = 1, int p = 0){
for (auto [v, w] : adj[u]){
if (v != p) STL(v, u);
}
if (u != 1 && adj[u].size() == 1){
S[u].insert({dist[u], depth[u]});
return;
}
int i = 0;
for (auto [v, w] : adj[u]){
if (v != p && S[v].size() > S[i].size()) i = v;
}
swap(S[i], S[u]);
int line = dist[u] + k, bend = k + dist[u] * 2;
auto it = S[u].lower_bound({line, 0});
if (it != S[u].end()){
pair<int, int> pos = *it;
if (pos.first == line)
ans = min(ans, pos.second - depth[u]);
}
for (auto [v, w] : adj[u]){
if (v == i or v == p) continue;
for (auto [Dis, Dep] : S[v]){
if (Dis == line) ans = min(ans, Dep - depth[u]);
auto it = S[u].lower_bound({bend - Dis, 0});
if (it != S[u].end()){
pair<int, int> pos = *it;
if (pos.first == bend - Dis)
ans = min(ans, pos.second + Dep - 2 * depth[u]);
}
}
for (auto i : S[v]) S[u].insert(i);
}
S[u].insert({dist[u], depth[u]});
}
int best_path(int NNN, int KKK, int ADJ[][2], int W[]){
n = NNN, k = KKK;
if (n == 1){
return -1;
}
for (int i = 0; i < n - 1; i++){
int u = ADJ[i][0] + 1, v = ADJ[i][1] + 1, w = W[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
dfs();
STL();
if (ans == 1e9) ans = -1;
return ans;
}
