#include "race.h"
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int kmax = 1000001;
const int nmax = 1000001;
vector <vector <pii> > g(nmax);
int d[nmax];
vector <bool> marked(nmax);
int k;
int n;
int ans = 1e9;
void DFS(int v, int e, int depth, int D){
ans = min(ans, d[k - depth] + D);
for(auto x: g[v]){
int to = x.f;
int len = x.s;
if(to == e || marked[to]) continue;
if(depth + len > k) continue;
DFS(to, v, depth + len, D + 1);
}
}
void upd(int v, int e, int depth, int D){
d[depth] = min(d[depth], D);
for(auto x : g[v]){
int to = x.f;
int len = x.s;
if(to == e || marked[to]) continue;
if(depth + len > k) continue;
upd(to, v, depth + len, D + 1);
}
}
void clear_dfs(int v, int e, int depth){
d[depth] = 1e9;
for(auto x : g[v]){
int to = x.f;
int len = x.s;
if(to == e || marked[to]) continue;
if(depth + len > k) continue;
clear_dfs(to, v, depth + len);
}
}
int sz[nmax];
void dfs(int v, int e){
sz[v] = 1;
for(auto x : g[v]){
int to = x.f;
if(marked[to] || to == e) continue;
dfs(to, v);
sz[v] += sz[to];
}
}
int find_cent(int v, int e, int n){
for(auto xx : g[v]){
int to = xx.f;
if(marked[to] || to == e) continue;
if(sz[to] * 2 >= n) return find_cent(to, v, n);
}
return v;
}
void decompose(int v){
dfs(v, v);
int x = find_cent(v, v, sz[v]);
//cout << 1;
d[0] = 0;
for(auto xx : g[x]){
int to = xx.f, len = xx.s;
if(marked[to]) continue;
if(len <= k){
DFS(to, x, len, 1);
upd(to, x, len, 1);
}
}
clear_dfs(x, x, 0);
marked[x] = true;
for(auto xx : g[x]){
int to = xx.f;
if(marked[to]) continue;
decompose(to);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
k = K;
int n = N;
for(int i = 0; i < N - 1; i++){
int u = H[i][0], v = H[i][1], w = L[i];
g[u].pb({v, w});
g[v].pb({u, w});
}
for(int i = 0; i <= k; i++){
d[i] = 1e9;
}
decompose(0);
if(ans == 1e9) ans = -1;
return ans;
}
