#include<bits/stdc++.h>
#include "race.h"
using namespace std;
const int maxN = 2e5 + 5;
int n, k;
struct edge{
int v, w;
};
vector<edge> e[maxN];
bool vis[maxN];
int step[maxN];long long dep[maxN];
int f[maxN][105];
namespace sub2{
int bfs(int u){
memset(vis, 0, sizeof(vis));
memset(step, 0, sizeof(step));
memset(dep, 0, sizeof(dep));
queue<int> q;
q.push(u);
vis[u] = 1;
int res = 1e9;
while (!q.empty()){
int u = q.front();
if (dep[u] == k){
res = min(res, step[u]);
}
q.pop();
for (auto v : e[u]){
if (vis[v.v]) continue;
vis[v.v] = 1;
step[v.v] = step[u] + 1;
dep[v.v] = dep[u] + v.w;
q.push(v.v);
}
}
return res;
}
int solve(){
int ans = 1e9;
for (int i = 0; i < n; i ++){
ans = min(ans, bfs(i));
}
if (ans >= n) ans = -1;
return ans;
}
}
namespace sub3{
int res = 1e9;
void dfs(int p, int u){
for (auto v : e[u]){
if (v.v == p) continue;
dfs(u, v.v);
for (int g = 0; g <= k; g ++) if (k - (g + v.w) >= 0 && (k - (g + v.w)) <= k)res = min(res, 1 + f[v.v][g] + f[u][k - (g + v.w)]);
for (int g = 0; g + v.w <= k; g ++){
f[u][g + v.w] = min(f[u][g + v.w], f[v.v][g] + 1);
}
}
res = min(res, f[u][k]);
f[u][0] = 0;
}
int solve(){
memset(f, 0x3f, sizeof(f));
dfs(0, 0);
if (res > n) return -1;
else return res;
}
}
namespace sub4{
struct query{
map<int, int> cur;
int hs;
};
int res = 1e9;
void pre_cal(int p, int u){
for (auto v : e[u]){
if (v.v == p) continue;
step[v.v] = step[u] + 1;
pre_cal(u, v.v);
}
}
query dfs(int p, int u){
query cur;
cur.hs = 0;
cur.cur[0] = step[u];
for (auto v : e[u]){
if (v.v == p) continue;
query tmp = dfs(u, v.v);
tmp.hs += v.w;
if (tmp.cur.size() > cur.cur.size()) swap(tmp, cur);
for (auto j : tmp.cur){
int real_fac = j.first + tmp.hs;
int st = cur.cur[(k - real_fac) - cur.hs];
if (st && j.second) res = min(res, st + j.second - 2 * step[u]);
// if (u == 0 && v.v == 5) cout << (k - real_fac) << '\n';
//if (st + j.second - 2 * step[u] == -6) cout << u << " " << st << " " << j.second << " " << v.v << '\n';
}
for (auto j : tmp.cur){
if (!j.second) continue;
int fuq = j.first + tmp.hs - cur.hs;
if (cur.cur[fuq] == 0){
cur.cur[fuq] = j.second;
}
else{
cur.cur[fuq] = min(cur.cur[fuq], j.second);
}
}
}
// if (u == 22) for (auto j : cur.cur) cout << j.first + cur.hs << " " << j.second << '\n';
return cur;
}
int solve(){
step[0] = 1;
pre_cal(0, 0);
dfs(0, 0);
if (res > n) return -1;
else return res;;
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N;
k = K;
for (int i = 0; i < n - 1; i ++){
int u, v, l;
u = H[i][0];
v = H[i][1];
l = L[i];
e[u].push_back({v, l});
e[v].push_back({u, l});
}
if (n <= 1000 && k <= 1000000){
return sub2::solve();
}
else if (n <= 200000 && k <= 100){
return sub3::solve();
}
else{
return sub4::solve();
}
}
