#include "race.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define fst first
#define snd second
#define pb push_back
#define forn(i,a,b) for(int i = a; i<b; i++)
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset(a,v,sizeof(a))
#define FIN ios::sync_with_stdio(0); cout.tie(); cin.tie(0);
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
template <typename L>
using iset = tree<L,null_type,less<L>,rb_tree_tag,tree_order_statistics_node_update>;
const int MAXN = 200000+5;
ll n;
ll k;
vector<pair<ll,ll>> adj[MAXN];
bool cen[MAXN];
ll subsz[MAXN];
unordered_map<ll,ll> path[MAXN];
void calcsz(ll nd, ll p){
subsz[nd]=1;
for(auto i:adj[nd])if(i.fst!=p && !cen[i.fst])calcsz(i.fst,nd);
for(auto i:adj[nd])if(i.fst!=p && !cen[i.fst])subsz[nd]+=subsz[i.fst];
}
void calcpath(ll nd, ll p, ll sz, ll dep){
path[nd].clear();
path[nd][sz]=dep;
for(auto i:adj[nd])if(i.fst!=p && !cen[i.fst]){
calcpath(i.fst,nd,sz+i.snd,dep+1);
}
for(auto i:adj[nd])if(i.fst!=p && !cen[i.fst]){
for(auto [szchild,rdep]:path[i.fst]) if(!path[nd][szchild]){
path[nd][szchild]=rdep;
}
}
}
ll find_centroid(ll nd, ll p){
for(auto i:adj[nd])if(i.fst!=p && !cen[i.fst]){
if(subsz[i.fst]*2>n){
return find_centroid(i.fst,nd);
}
}
cen[nd]=true;
return nd;
}
ll rres = 1000000000;
void solve(){
queue<ll> cola; cola.push(0);
while(!cola.empty()){
ll nd=cola.front();
cola.pop();
calcsz(nd,-1);
ll c = -1;
if(subsz[nd]>1) c=find_centroid(nd,-1);
if(c==-1) continue;
//cout<<"Nuevo centroide "<<c<<'\n';
ll res = 1000000000;
unordered_map<ll,ll> paths;
for(auto i:adj[c]) if(!cen[i.fst]){
calcpath(i.fst,c,i.snd,1);
for(auto [szchild,rdep]:path[i.fst]) if(paths[k-szchild]){
res=min(res,rdep+paths[k-szchild]);
}
for(auto [szchild,rdep]:path[i.fst]) if(!paths[szchild]){
paths[szchild]=rdep;
if(szchild==k) res=min(res,rdep);
}else{
paths[szchild]=min(paths[szchild],rdep);
}
cola.push(i.fst);
}
rres=min(rres,res);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
//cout<<"inica\n";
FIN;
n = N;
k = K;
forn(i,0,n-1){
adj[H[i][0]].pb({H[i][1],L[i]});
adj[H[i][1]].pb({H[i][0],L[i]});
}
//cout<<"llamando a solve\n";
solve();
// cout<<rres<<'\n';
return (rres!=1000000000?rres:-1);
}
