#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define fr first
#define sc second
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)
const int nmax = 200005;
int tot;
int sub[nmax], used[nmax], ans = 1e9;
vector <pair<int,int>> nod[nmax];
void calc(int s, int par = 0){
sub[s] = 1;
for(auto it : nod[s]){
if(used[it.fr] == 0 && it.fr != par){
calc(it.fr, s);
sub[s] += sub[it.fr];
}
}
}
int find_centroid(int s, int nec, int par = 0){
for(auto it : nod[s]){
if(used[it.fr] == 0 && it.fr != par && sub[it.fr] > nec){
return find_centroid(it.fr, nec, s);
}
}
return s;
}
void dfs(int s, map<int,int>&aux, int len, int nredge, int par = 0){
if(aux.count(len) == 0){
aux[len] = nredge;
}
else{
aux[len] = min(aux[len], nredge);
}
for(auto it : nod[s]){
if(it.fr != par && used[it.fr] == 0){
dfs(it.fr, aux, len + it.sc, nredge + 1, s);
}
}
}
void centroid(int s){
calc(s);
int centr = find_centroid(s, sub[s] / 2);
map<int, int> aux, fin;
fin[0] = 0;
used[centr] = 1;
for(auto it : nod[centr]){
if(used[it.fr] == 0){
dfs(it.fr, aux, it.sc, 1);
for(auto it1 : aux){
if(fin.count(tot - it1.fr) == 1){
ans = min(ans, it1.sc + fin[tot - it1.fr]);
}
}
for(auto it1 : aux){
if(fin.count(it1.fr) == 0){
fin[it1.fr] = it1.sc;
}
else{
fin[it1.fr] = min(fin[it1.fr], it1.sc);
}
}
aux.clear();
centroid(it.fr);
}
}
}
int best_path(int N, int K, int H[][2], int L[]){
tot = K;
for(int i=1;i<N;i++){
nod[H[i-1][0]].push_back({H[i-1][1], L[i-1]});
nod[H[i-1][1]].push_back({H[i-1][0], L[i-1]});
}
centroid(0);
if(ans == 1e9){
return -1;
}
else{
return ans;
}
}
