#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int mxn = 200005;
pii dist[1000005];
vector<pii> adj[mxn];
int SOL = INT_MAX, kk;
int sz[mxn];
bool rem[mxn];
int getsz(int cur, int p = -1) {
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 = -1) {
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 cent, int cur, int p, bool fil, int dep, int d2 = 1) {
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 SOL = (dist[kk-dep].first == cent ? min(dist[kk-dep].second+d2, SOL) : SOL);
for(pii e:adj[cur])
if(e.first != p && !rem[e.first])
sol(cent, e.first, cur, fil, dep+e.second, d2+1);
}
void decompose(int cur = 1) {
int cent = getcent(getsz(cur), cur);
rem[cent] = 1;
dist[0] = {cent, 0};
for(pii e:adj[cent]) {
sol(cent, e.first, cent, false, e.second);
sol(cent, e.first, cent, true, e.second);
}
//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[]) {
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();
return (SOL > N ? -1 : SOL);
}
