#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define ed <<endl;
vector<vector<pair<int, int>>> adj(2e5+5);
vector<int> sz(2e5+5);
int N;
int K;
int cur = -1;
vector<int> forb(2e5+5);
int findCentroid(int n, int node, int par){
// cerr << imie(node) imie(par) ed;
if(n == 1){
cur = node;
return 0;
}
sz[node] = 1;
bool ok = 1;
for(int i=0;i<(int)adj[node].size();i++){
if(cur != -1){
return 0;
}
int v=adj[node][i].first;
if(v != par && !forb[v]){
sz[node] += findCentroid(n, v, node);
if(sz[v] > n / 2) ok = 0;
}
}
if(n - sz[node] > n / 2){
ok = 0;
}
if(ok){
cur = node;
}
return sz[node];
}
int ans = 2e5+5;
//map<cost, edgecount>
void dfs(int node, int par, int dist, int cost, map<int, int> &global){
int k=K;
if(cost > K){
return;
}
if(cost == k){
ans = min(ans, dist);
return;
}
if(global[k-cost] != 0){
ans = min(ans, global[k-cost]+dist);
}
for(int i=0;i<(int)adj[node].size();i++){
int v = adj[node][i].first;
if(!forb[v] && v != par){
dfs(v,par,dist+1,cost+adj[node][i].second, global);
}
}
if(global[cost] == 0){
global[cost] = dist;
}
global[cost] = min(global[cost], dist);
}
void mysol(int node){
int cnt = 0;
function<void(int, int)> mdfs = [&](int curnode, int par){
cnt++;
for(int i=0;i<(int)adj[curnode].size();i++){
int v = adj[curnode][i].first;
if(!forb[v] && v != par){
mdfs(v, curnode);
}
}
};
mdfs(node, -1);
map<int, int> global;
cur = -1;
findCentroid(cnt, node, -1);
forb[cur] = 1;
dfs(cur, -1, 0, 0, global);
// cerr << imie(cur) imie(cnt) ed;
int me = cur;
for(int i=0;i<(int)adj[me].size();i++){
int v = adj[me][i].first;
if(!forb[v]){
mysol(v);
}
}
}
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 = h[i][0];
int v = h[i][1];
adj[u].push_back({v, l[i]});
adj[v].push_back({u, l[i]});
}
mysol(0);
return (ans > n ? -1 : ans);
}
