#include<bits/stdc++.h>
#include "race.h"
using namespace std;
constexpr int MAXN = 2*1e5 + 5, MAXK = 1e6 + 5, INF = 1e8;
bool visited[MAXN];
int c[MAXN], k, mini[MAXK];
vector<int> edges[MAXN], w[MAXN];
int cnt(int id){
visited[id] = 1;
c[id] = 1;
for(int v : edges[id]) if(!visited[v]) c[id] += cnt(v);
visited[id] = 0;
return c[id];
}
int init(int id, int n, int p = -1){
for(int v : edges[id]) if(c[v] > n/2 && !visited[v] && p != v) return init(v, n, id);
return id;
}
int centroid(int id){
return init(id, cnt(id));
}
int calc(int id, int len, int lvl = 1, int p = -1){
int ret = INF;
if(len <= k) ret = min(ret, mini[k-len] + lvl);
for(int i = 0; i < edges[id].size(); i++){
int v = edges[id][i];
if(!visited[v] && v != p) ret = min(ret, calc(v, min(INF, len + w[id][i]), lvl + 1, id));
}
return ret;
}
void add(int id, int len, int lvl = 1, int p = -1){
if(len < MAXK) mini[len] = min(mini[len], lvl);
for(int i = 0; i < edges[id].size(); i++){
int v = edges[id][i];
if(!visited[v] && p != v) add(v, min(INF, len + w[id][i]), lvl + 1, id);
}
}
void res(int id, int len = 0, int p = -1){
if(len < MAXK) mini[len] = INF;
for(int i = 0; i < edges[id].size(); i++){
int v = edges[id][i];
if(!visited[v] && p != v) res(v, min(INF, len + w[id][i]), id);
}
}
int db(int id){
int ret = INF;
mini[0] = 0;
for(int i = 0; i < edges[id].size(); i++){
int v = edges[id][i];
if(visited[v]) continue;
ret = min(ret, calc(v, w[id][i], 1, id));
add(v, w[id][i], 1, id);
}
res(id);
return ret;
}
int process(int id){
int ret = db(id);
visited[id] = 1;
for(int v : edges[id]) if(!visited[v]) ret = min(ret, process(centroid(v)));
return ret;
}
int best_path(int N, int K, int H[][2], int L[])
{
fill(mini, mini + MAXK, INF);
k = K;
for(int i = 0; i < N-1; i++){
edges[H[i][0]].push_back(H[i][1]);
w[H[i][0]].push_back(L[i]);
swap(H[i][0], H[i][1]);
edges[H[i][0]].push_back(H[i][1]);
w[H[i][0]].push_back(L[i]);
}
int ret = process(centroid(0));
return (ret == INF ? -1 : ret);
}
