#include <bits/stdc++.h>
#include "race.h"
using namespace std;
#define ll long long
const ll mmod = 998244353;
#define vl vector<long long>
#define vll vector<vector<long long>>
#define pl pair<long long, long long>
#define vb vector<bool>
vector<vector<pl>> graf;
vb center;
vl sizes;
ll minimum = 1e15;
ll getsize(ll v, ll u){
ll s = 1;
for (auto x : graf[v]){
if (center[x.first] == false && x.first != u){
s += getsize(x.first, v);
}
}
sizes[v] = s;
return s;
}
ll findcentroid(ll v, ll u, ll n){
ll a = 1;
for (auto x : graf[v]){
if (center[x.first] == false && x.first != u){
a = findcentroid(x.first, v, n);
if (a!=-1){
return a;
}
}
}
if (sizes[v] >= n/2){
return v;
}
else{
return -1;
}
}
void dists(ll v, ll u, ll d, ll depth, vector<pl>& dist, ll k){
dist.push_back({d, depth});
for (auto x : graf[v]){
if (center[x.first] == false && x.first != u){
if (d + x.second <= k){
dists(x.first, v, d + x.second, depth + 1, dist, k);
}
}
}
}
void decompose(ll v, ll k){
ll comp = getsize(v,-1);
ll c = findcentroid(v, -1, comp);
center[c] = true;
vector<pl> dist = {{0,0}};
for (auto x : graf[c]){
vector<pl> newdist;
if (center[x.first] == false){
dists(x.first, c, x.second, 1, newdist, k);
}
sort(newdist.begin(), newdist.end());
ll l = 0;
ll r = newdist.size()-1;
while (l < (ll)dist.size() && r >= 0){
ll suma = dist[l].first + newdist[r].first;
if (suma == k){
minimum = min(minimum, dist[l].second + dist[r].second);
r--;
}
else if (suma < k){
l++;
}
else{
r--;
}
}
if (dist.size() < newdist.size()){
swap(dist, newdist);
}
for (ll i = 0; i < newdist.size(); i++){
dist.push_back(newdist[i]);
}
sort(dist.begin(), dist.end());
}
for (auto x : graf[c]){
if (center[x.first] == false){
decompose(x.first, k);
}
}
}
int best_path(int N, int K, int H[][2], int L[]){
ll n = N; ll k = K;
graf.clear(); center.clear(); sizes.clear(); minimum = 1e14;
graf.resize(n);
center.resize(n, false);
sizes.resize(n,0);
for (ll i = 0; i < n-1; i++){
ll a,b;
a = H[i][0]; b = H[i][1];
ll c = L[i];
graf[a].push_back({b,c});
graf[b].push_back({a,c});
}
decompose(0, k);
if (minimum >= 1e14) return -1;
return (int)minimum;
}
