/**************************************************************
Submitted By: Mayuresh N. Patle
Written On: Saturday, July 16, 2022
**************************************************************/
#include "race.h"
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define mod1 998244353
#define rep(i,s,e) for(i=s;i<e;++i)
#define repr(i,s,e) for(i=s;i>e;--i)
#define fp(i) fixed<<setprecision(i)
#define in(a) for(auto &ghe:a) cin>>ghe;
#define in2d(a) for(auto &ghe:a) for(auto &he:ghe) cin>>he;
#define out(a) for(auto &ghe:a) cout<<ghe<<" ";cout<<endl;
#define out2d(a) {for(auto &he:a) {out(he)}}
#define loop(i,a) for(auto &i:a)
#define inrange(i,j,k) (((i)<=(j)) && ((j)<(k)))
#define make(a,i) memset(a,i,sizeof(a))
#define chk(x) cerr<<(#x)<<":"<<(x)<<endl;
#define chk2(x,y) cerr<<(#x)<<":"<<(x)<<" "<<(#y)<<":"<<(y)<<endl;
#define chk3(x,y,z) cerr<<(#x)<<":"<<(x)<<" "<<(#y)<<":"<<(y)<<" "<<(#z)<<":"<<(z)<<endl;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector <ll> vll;
typedef vector <float> vf;
typedef vector <ld> vld;
#define pb push_back
#define pob() pop_back()
typedef pair <ll,ll> pll;
#define F first
#define S second
#define mp(a,b) make_pair(a,b)
typedef vector <pll> vp;
typedef vector <bool> flags;
#define all(v) begin(v),end(v)
#define amin(var, val) var = (val)<var ? (val) : var
#define amax(var, val) var = (val)>var ? (val) : var
#define xiny(x,y) (y.find(x)!=y.end())
const ll maxN = 2e5+1;
class edge{
public:
ll u,v,w;
edge(){}
edge(ll u, ll v, ll w): u(u), v(v), w(w){}
ll op(ll x) {return u^v^x;}
};
vll G[maxN];
vector <edge> e;
map <ll, ll> m[maxN];
ll k;
pll dfs(ll v, ll p, int& ans)
{
ll da=0, la=0;
m[v][0] = 0;
loop(i, G[v])
{
if(ans==1) return {0,0};
ll u=e[i].op(v), w=e[i].w;
if(u==p) continue;
if(w==k)
{
ans=1;
return {0,0};
}
pll res = dfs(u, v, ans);
ll cda = w + res.F;
ll cla = 1 + res.S;
if(m[u].size()>m[v].size())
{
swap(m[u], m[v]);
swap(da, cda);
swap(la, cla);
}
loop(p, m[u])
{
ll rd = p.F + cda;
ll rl = p.S + cla;
if(rd == k) amin(ans, rl);
else if(rd < k)
{
ll reqd = k - rd - da;
if(xiny(reqd, m[v])) amin(ans, rl + m[v][reqd] + la);
}
}
loop(p, m[u])
{
ll rd = p.F + cda;
ll rl = p.S + cla;
if(rd < k)
{
rd -= da;
rl -= la;
if(xiny(rd, m[v])) amin(m[v][rd], rl);
else m[v][rd] = rl;
}
}
}
return {da, la};
}
int best_path(int n, int K, int H[][2], int L[])
{
k=K;
ll i;
rep(i,0,n-1)
{
ll u=H[i][0], v=H[i][1], w=L[i];
G[u].pb(e.size());
G[v].pb(e.size());
e.pb(edge(u,v,w));
}
int ans = maxN;
dfs(0, -1, ans);
if(ans==maxN) ans=-1;
return ans;
}
