#include<bits/stdc++.h>
using namespace std;
const int N = 200001;
const int K = 1000001;
int n, k, global_answer;
int split_node, current_max;
int book_keeping;
int H[N][2];
int L[N];
int processed[N];
int size2[N];
int achievable[K];
int minimum_paths[K];
vector<pair<int, int> > adj[N];
void calc_size(int current, int parent){
size2[current] = 0;
int i;
for (i = 0; i < (int)adj[current].size(); i++){
if (!processed[adj[current][i].first] && adj[current][i].first != parent){
calc_size(adj[current][i].first, current);
size2[current] += 1 + size2[adj[current][i].first];
}
}
}
void select_split_node(int current, int parent, int total){
int node_max = (total - size2[current] - 1);
int i;
for (i = 0; i < (int)adj[current].size(); i++){
if (!processed[adj[current][i].first] && adj[current][i].first != parent){
select_split_node(adj[current][i].first, current, total);
node_max = max(node_max, 1 + size2[adj[current][i].first]);
}
}
if (node_max < current_max)
{
split_node = current;
current_max = node_max;
}
}
void dfs_from_node(int current, int parent, int current_cost, int current_length, int fill){
if (current_cost > k)
return;
if (!fill){
if (achievable[k - current_cost] == book_keeping){
if (current_length + minimum_paths[k - current_cost] < global_answer || global_answer == -1){
global_answer = current_length + minimum_paths[k - current_cost];
}
}
if (current_cost == k){
if (current_length < global_answer || global_answer == -1){
global_answer = current_length;
}
}
}
else{
if (achievable[current_cost] < book_keeping)
{
achievable[current_cost] = book_keeping;
minimum_paths[current_cost] = current_length;
}
else if (current_length < minimum_paths[current_cost])
{
achievable[current_cost] = book_keeping;
minimum_paths[current_cost] = current_length;
}
}
int i;
for (i = 0; i < (int)adj[current].size(); i++){
if (!processed[adj[current][i].first] && adj[current][i].first != parent){
dfs_from_node(adj[current][i].first, current, current_cost + adj[current][i].second, current_length + 1, fill);
}
}
}
void process(int current){
calc_size(current, -1);
if (size2[current] <= 1){
return;
}
split_node = -1;
current_max = size2[current] + 3;
select_split_node(current, -1, size2[current] + 1);
book_keeping++;
int i;
for (i = 0; i < (int)adj[split_node].size(); i++){
if (!processed[adj[split_node][i].first]){
dfs_from_node(adj[split_node][i].first, split_node, adj[split_node][i].second, 1, 0);
dfs_from_node(adj[split_node][i].first, split_node, adj[split_node][i].second, 1, 1);
}
}
int local_split_node = split_node;
processed[split_node] = 1;
for (i = 0; i < (int)adj[local_split_node].size(); i++){
if (!processed[adj[local_split_node][i].first]){
process(adj[local_split_node][i].first);
}
}
}
int best_path(int _N, int _K, int H[][2], int L[]){
memset(processed, 0, sizeof processed);
memset(achievable, 0, sizeof achievable);
memset(minimum_paths, 0, sizeof minimum_paths);
n = _N;
k = _K;
book_keeping = 0;
int i;
for (i = 0; i < n - 1; i++){
adj[H[i][0]].push_back(make_pair(H[i][1], L[i]));
adj[H[i][1]].push_back(make_pair(H[i][0], L[i]));
}
global_answer = -1;
process(0);
return global_answer;
}
