#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
int n;
long long k_target;
vector<pair<long long, int>> dt[MAXN];
int depth[MAXN], sz[MAXN];
int arr[MAXN], tin[MAXN], tout[MAXN], id;
long long t[MAXN];
map<long long, int> luu;
int kq = 1e9;
void prpdfs(int u, int p){
sz[u] = 1;
arr[++id] = u;
tin[u] = id;
depth[u] = depth[p] + 1;
for(auto &[w, v] : dt[u]) if(v != p){
t[v] = t[u] + w;
prpdfs(v, u);
sz[u] += sz[v];
}
tout[u] = id;
}
void sack(int u, int p, bool keep){
int big = 0;
for(auto &[w, v] : dt[u]) if(v != p && sz[v] > sz[big]) big = v;
for(auto &[w, v] : dt[u]) if(v != p && v != big) sack(v, u, 0);
if(big != 0) sack(big, u, 1);
long long kk = k_target + t[u];
if(luu.count(kk)){
kq = min(kq, luu[kk] - depth[u]);
}
if(!luu.count(t[u])) luu[t[u]] = depth[u];
else luu[t[u]] = min(luu[t[u]], depth[u]);
for(auto &[w, v] : dt[u]) if(v != p && v != big){
for(int idx = tin[v]; idx <= tout[v]; idx++){
int x = arr[idx];
long long kkk = k_target + 2LL * t[u] - t[x];
if(luu.count(kkk)){
kq = min(kq, luu[kkk] + depth[x] - 2*depth[u]);
}
}
for(int idx = tin[v]; idx <= tout[v]; idx++){
int x = arr[idx];
if(!luu.count(t[x])) luu[t[x]] = depth[x];
else luu[t[x]] = min(luu[t[x]], depth[x]);
}
}
if(!keep){
for(int idx = tin[u]; idx <= tout[u]; idx++){
int v = arr[idx];
luu.erase(t[v]);
}
}
}
// Đây là hàm hệ thống Grader sẽ tự động gọi để chấm điểm
int best_path(int N, int K, int H[][2], int L[]) {
// 1. Khởi tạo lại các biến toàn cục (đề phòng Grader gọi hàm nhiều lần)
n = N;
k_target = K;
kq = 1e9;
id = 0;
luu.clear();
for (int i = 0; i <= n; i++) {
dt[i].clear();
depth[i] = 0;
sz[i] = 0;
}
// 2. Chuyển đổi dữ liệu input của Grader thành danh sách kề (chuyển về 1-based index)
for (int i = 0; i < N - 1; i++) {
int u = H[i][0] + 1;
int v = H[i][1] + 1;
long long w = L[i];
dt[u].emplace_back(w, v);
dt[v].emplace_back(w, u);
}
// 3. Gọi hàm xử lý chính
t[1] = 0;
depth[0] = 0; // Đỉnh giả 0 làm mốc depth
prpdfs(1, 0);
sack(1, 0, 1);
// 4. Trả về kết quả thay vì cout
if (kq > 1e6) return -1;
return kq;
}
