#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define F first
#define S second
#define MP make_pair
#define pii pair<int,int>
#define vi vector<int>
#define all(x) x.begin(),x.end()
#define vvi vector<vector<int>>
#define loop(i,a,b) for(int i = a; i <= b; i++)
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define _ ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
using namespace std;
const int OO = 1e9;
const int N = 2e5 + 5;
const int K = 1e6 + 5;
//best depth available for current weight
int curK, sz[N], best[K];
bool rem[N];
vector<pair<int,int>> adj[N];
void preSz(int u, int par)
{
sz[u] = 1;
for(auto e:adj[u])
{
if(e.F == par || rem[e.F])
continue;
preSz(e.F, u);
sz[u] += sz[e.F];
}
}
int getCen(int u, int par, int subSz)
{
int mxSz = subSz - sz[u];
int ret = -1;
for(auto e:adj[u])
{
if(e.F == par || rem[e.F])
continue;
ret = max(ret, getCen(e.F, u, subSz));
mxSz = max(mxSz, sz[e.F]);
}
if(mxSz <= subSz / 2)
ret = u;
return ret;
}
void update(int u, int par, int curD, int curW, bool add)
{
if(curW > curK)
return;
if(add)
best[curW] = min(best[curW], curD);
else
best[curW] = OO;
for(auto e:adj[u])
{
if(e.F == par || rem[e.F])
continue;
update(e.F, u, curD+1, curW + e.S, add);
}
}
int solve(int u, int par, int curD, int curW)
{
if(curW > curK)
return OO;
int ans = curD + best[curK - curW];
for(auto e:adj[u])
{
if(e.F == par || rem[e.F])
continue;
ans = min(ans, solve(e.F, u, curD+1, curW+e.S));
}
return ans;
}
int solveCen(int cen)
{
int ans = OO;
for(auto e:adj[cen])
{
if(rem[e.F])
continue;
update(e.F, cen, 1, e.S, true);
ans = min(ans, solve(e.F,cen,1,e.S));
}
return ans;
}
int decompose(int node)
{
preSz(node, 0);
int cen = getCen(node, 0, sz[node]);
int curAns = solveCen(cen);
update(cen, 0, 0, 0,false);
rem[cen] = true;
for(auto e:adj[node])
{
if(rem[e.F])
continue;
curAns = min(curAns, decompose(e.F));
}
return curAns;
}
int best_path(int nn, int kk, int H[][2], int L[]){
curK = kk;
for(int i=0; i<nn-1; i++){
adj[H[i][0]+1].pb({H[i][1]+1, L[i]});
adj[H[i][1]+1].pb({H[i][0]+1, L[i]});
}
for(int i=0; i<K; i++) best[i] = OO;
int ans = decompose(1);
return ans == OO ? -1 : ans;
}
