#include <iostream>
#include <utility>
#include <vector>
#include <cassert>
using namespace std;
using pii = pair<int, int>;
const int mxn = 200005;
pii dist[1000005];
vector<pii> adj[mxn];
int SOL = 1000005, kk;
int sz[mxn];
int cent, d2 = 1, dep;
bool rem[mxn], fil;
int getsz(int cur, int p) {
sz[cur] = 1;
for(pii e:adj[cur])
if(e.first != p && !rem[e.first])
sz[cur] += getsz(e.first, cur);
return sz[cur];
}
int getcent(int tgt, int cur, int p) {
for(pii e:adj[cur])
if(e.first != p && !rem[e.first] && sz[e.first] > tgt/2)
return getcent(tgt, e.first, cur);
return cur;
}
void sol(int cur, int p) {
if(dep > kk) return ;
if(fil) {
if(dist[dep].first == cent)
dist[dep].second = min(d2, dist[dep].second);
else
dist[dep] = {cent, d2};
}
else if(dist[kk-dep].first == cent) SOL = min(dist[kk-dep].second+d2, SOL);
d2++;
for(pii e:adj[cur])
if(e.first != p && !rem[e.first])
{
dep += e.second;
sol(e.first, cur);
dep -= e.second;
}
d2--;
}
void decompose(int cur) {
cent = getcent(getsz(cur, -1), cur, -1);
rem[cent] = 1;
dist[0] = {cent, 0};
for(pii e:adj[cent]) {
if(rem[e.first]) continue;
dep = e.second;
fil = 0; sol(e.first, cent);
fil = 1; sol(e.first, cent);
}
//cout << SOL << ' ' << cent << '\n';
for(pii e:adj[cent])
if(!rem[e.first]) decompose(e.first);
}
int best_path(int N, int K, int H[][2], int L[]) {
//assert(N <= 150'000);
kk = K;
fill(dist, dist+1000003, pii(-1, -1));
for(int i=0;i<N-1;i++) {
adj[H[i][0]].emplace_back(H[i][1], L[i]);
adj[H[i][1]].emplace_back(H[i][0], L[i]);
}
decompose(1);
return (SOL > N ? -1 : SOL);
}
