#include "race.h"
#include <bits/stdc++.h>
#include <climits>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define pii pair<int,int>
#define vi vector<int>
#define vpii vector<pii>
#define loop(i,n) sloop(0,i,n)
#define sloop(s, i, n) for(int i=(s);i<(n);i++)
#define rloop(i,n) rsloop(0,i,n)
#define rsloop(s,i,n) for(int i=(n);i-->(s);)
#define all(v) (v).begin(),(v).end()
#define nie {cout<<"No\n";return;}
#define tak {cout<<"Yes\n";return;}
#ifdef DEBUG
#define DBG cout << __LINE__ << endl;
#else
#define DBG
#endif
//int xses[8] = {-1,1,0,0,-1,1,1,-1};
//int yses[8] = {0,0,-1,1,-1,1,-1,1};
#define int ll
vector<vpii> graf;
int k;
int res = LLONG_MAX;
pair<pii,map<int,int>> dfs(int node,int p=-1){
pair<pii,map<int,int>> cur;
cur.F = {0,0};
for(pii i:graf[node]){
if(i.F==p)continue;
if(i.S==k){
res=1;
}
auto [chng,a] = dfs(i.F,node);
chng.F+=i.S;chng.S++;
a[i.S-chng.F]=1-chng.S;
if(cur.S.size()<a.size()){
swap(cur.S,a);
swap(chng,cur.F);
}
for(pii j:a){
if(cur.S.count(k-(j.F+chng.F)-cur.F.F)){
res = min(res,j.S+chng.S+cur.S[k-(j.F+chng.F)-cur.F.F]+cur.F.S);
}
}
/*
cout<<node<<'\n';
for(pii z:cur.S){
cout<<z.F+cur.F.F<<' '<<z.S+cur.F.S<<'\n';
}
cout<<node<<'\n';
for(pii j:a){
cout<<j.F+chng.F<<' '<<j.S+chng.S<<'\n';
}
*/
for(pii j:a){
int u = j.F+chng.F - cur.F.F;
int v = j.S+chng.S - cur.F.S;
if(cur.S.count(u)){
cur.S[u]=min(cur.S[u],v);
}else{
cur.S[u]=v;
}
}
}
if(cur.S.count(k-cur.F.F)){
res=min(res,cur.S[k-cur.F.F]+cur.F.S);
}
/*
for(pii i:cur.S){
cout<<i.F+cur.F.F<<' '<<i.S+cur.F.S<<'\n';
}
*/
return cur;
}
#undef int
int best_path(int N, int K, int H[][2], int L[])
{
int n = N;
k = K;
res=LLONG_MAX;
graf.assign(n,vector<pair<ll,ll>>());
loop(i,n-1){
int a = H[i][0];
int b = H[i][1];
int w = L[i];
graf[a].pb({b,w});
graf[b].pb({a,w});
}
dfs(0);
if(res==LLONG_MAX)res=-1;
return (int)res;
}
