#include "race.h"
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define pb push_back
#define s second
#define f first
using namespace std;
typedef pair<int, int> pii;
const int MxN=2e5+10;
vector<pii> ad[MxN];
bool v[MxN];
int sz[MxN];
void get_sizes(int u, int pst=-1)
{
sz[u]=1;
for(auto it : ad[u]){
int x=it.f;
if(v[x] || x==pst) continue;
get_sizes(x, u);
sz[u]+=sz[x];
}
}
int get_centroid(int u, int max_size, int pst=-1)
{
for(auto it : ad[u]){
int x=it.f;
if(v[x] || x==pst) continue;
if(sz[x]>max_size/2){
return get_centroid(x, max_size, u);
}
}
return u;
}
void trav(int u, multiset<pii> &st, int w_sum, int cn, int pst=-1)
{
st.insert({w_sum,cn});
for(auto it : ad[u]){
int x=it.f, w=it.s;
if(v[x] || x==pst) continue;
trav(x, st, w_sum+w, cn+1, u);
}
}
int ans=1e9;
void calc_paths(int u, int k)
{
int nb=ad[u].size();
multiset<pii> st[nb], full;
FOR(i, 0, nb)
{
int x=ad[u][i].f, w=ad[u][i].s;
if(v[x]) continue;
trav(x, st[i], w, 1, u);
for(auto it : st[i]){
full.insert(it);
}
}
full.insert({0,0});
// cout << u << ":\n";
// for(auto it : full){
// cout << it.f << " " << it.s << '\n';
// }
FOR(i, 0, nb)
{
for(auto it : st[i]){
full.erase(full.find(it));
}
for(auto it : st[i]){
auto fnd=full.lower_bound({k-it.f,0});
if(fnd!=full.end() && (*fnd).f==k-it.f){
ans=min(ans, it.s+(*fnd).s);
}
}
for(auto it : st[i]){
full.insert(it);
}
}
}
void dfs(int u, int k)
{
get_sizes(u);
int ct=get_centroid(u, sz[u]);
// cout << u << " " << ct << endl;
calc_paths(ct, k);
v[ct]=true;
for(auto it : ad[ct]){
int x=it.f;
if(v[x]) continue;
dfs(x, k);
}
}
int best_path(int n, int k, int h[][2], int l[])
{
FOR(i, 0, n-1)
{
ad[h[i][0]].pb({h[i][1],l[i]});
ad[h[i][1]].pb({h[i][0],l[i]});
}
dfs(0, k);
return (ans==int(1e9)?-1:ans);
}
