#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define sz size()
typedef long long ll;
ll k,ans =1e18;
const int N = 200002;
vector<pair<ll,ll> > v[N];
ll siz[N], freq[N*5],vis[N];
void build(ll x, ll par)
{
siz[x] = 1;
for(int i = 0; i < v[x].sz; i++)
{
ll nn = v[x][i].F;
if(nn==par||vis[nn]) continue;
build(nn,x);
siz[x]+=siz[nn];
}
}
ll findcn(ll x, ll par, ll m)
{
for(int i = 0; i < v[x].sz; i++)
{
ll nn = v[x][i].F;
if(nn==par||vis[nn]) continue;
if(siz[nn]>m/2) return findcn(nn,x,m);
}
return x;
}
void get(ll x, ll par, ll w , ll d)
{
if(w<=k)
ans=min(ans,freq[k-w]+d);
for(int i = 0 ; i < v[x].sz; i++)
{
ll nn = v[x][i].F;
if(nn==par||vis[nn]) continue;
get(nn,x,w+v[x][i].S,d+1);
}
}
void upd(ll x, ll par, ll w,ll d ,ll tp)
{
if(w<=k&&tp==1)
freq[w] = min(freq[w],d);
else if(w<=k)
freq[w] = 1e18;
for(int i = 0 ; i < v[x].sz; i++)
{
ll nn = v[x][i].F;
if(nn==par||vis[nn]) continue;
upd(nn,x,w+v[x][i].S,d+1,tp);
}
}
void dfs(ll x)
{
build(x,-1);
ll cent = findcn(x, -1, siz[x]/2);
//cout << cent << endl;
vis[cent] = 1;
for(int i = 0; i < v[cent].sz; i++)
{
if(vis[v[cent][i].F]) continue;
get(v[cent][i].F,-1,v[cent][i].S,1);
upd(v[cent][i].F,-1,v[cent][i].S,1,1);
//for(int i = 0; i <= k; i++) cout << freq[i] << " "; cout << ans; cout << endl;
}
ans = min(ans,freq[k]);
for(int i = 0; i < v[cent].sz; i++)
{
if(vis[v[cent][i].F]) continue;
upd(v[cent][i].F,-1,v[cent][i].S,1,1-1);
}
for(int i = 0; i < v[cent].sz; i++)
if(!vis[v[cent][i].F]) dfs(v[cent][i].F);
}
int best_path(int N, int K, int H[][2], int L[])
{
// make the graph
// dfs(ll x) : build , findcn , make it vis , go from childls and make get upd , theen upd2
// build(ll x, ll par), findcn(ll x, ll par)
// get
// update
k = K;
for(int i = 1; i <= k; i++) freq[i] = 1e18;
for(int i = 0; i < N-1; i++)
{
ll x = H[i][0] , y = H[i][1], z = L[i];
v[x].push_back({y,z});
v[y].push_back({x,z});
}
dfs(0);
if(ans>=1e18) return -1;
return ans;
}
