#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define num long long
#define di pair<int, num>
#define sdi set<di>
#define graph vector<sdi>
#define idata vector<int>
#define INF 1e18
graph roads;
int nbNodes, pathLength;
struct MMap {
map<num, num> m;
bool has (num depth) {
return m.find(depth) != m.end();
}
num get (num depth) {
return (*(m.find(depth))).second;
}
void set (num depth, num value) {
if (has(depth)) {
value = min(value, get(depth));
m.erase(depth);
}
m.insert({ depth, value });
}
void clear () {
m.clear();
}
void show () {
for (auto u : m)
printf("%lld:%lld ", u.first, u.second);
cout << endl;
}
};
struct CDecompose {
num answer = 1e18;
idata subtree;
MMap min_map;
void init () {
subtree.resize(nbNodes);
build (0, -1);
}
void build (int node, int parent) {
int compSize = w_dfs(node, parent);
int centroid = c_dfs(node, parent, compSize >> 1);
min_map.set(0, 0);
for (di next : roads[centroid]) {
comp(next.first, centroid, next.second, 1);
fill(next.first, centroid, next.second, 1);
}
min_map.clear();
while (roads[centroid].size() != 0) {
di err = *roads[centroid].begin();
roads[centroid ].erase(err);
roads[err.first].erase({ centroid, err.second });
build (err.first, -1);
}
}
int w_dfs (int node, int parent) {
subtree[node] = 1;
for (di next : roads[node]) {
if (next.first == parent) continue ;
subtree[node] += w_dfs(next.first, node);
}
return subtree[node];
}
int c_dfs (int node, int parent, int desired) {
for (di next : roads[node])
if (next.first != parent && desired <= subtree[next.first])
return c_dfs(next.first, node, desired);
return node;
}
void comp (int node, int parent, num length, int depth) {
if (length > pathLength) return ;
if (depth > answer) return ;
if (min_map.has(pathLength - length)) {
answer = min(
answer,
min_map.get(pathLength - length) + depth
);
}
for (di next : roads[node]) {
if (next.first == parent) continue ;
comp(next.first, node, length + next.second, depth + 1);
}
}
void fill (int node, int parent, num length, int depth) {
if (length > pathLength) return ;
if (depth > answer) return ;
min_map.set(length, depth);
for (di next : roads[node]) {
if (next.first == parent) continue ;
fill(next.first, node, length + next.second, depth + 1);
}
}
};
int best_path(int N, int K, int H[][2], int L[])
{
nbNodes = N;
pathLength = K;
roads.resize(nbNodes);
for (int idRoad = 0; idRoad + 1 < nbNodes; idRoad ++) {
int a, b; num l;
a = H[idRoad][0];
b = H[idRoad][1];
l = L[idRoad];
roads[a].insert({ b, l });
roads[b].insert({ a, l });
}
CDecompose dec;
dec.init();
return dec.answer == INF ? -1 : dec.answer;
}
/*int main () {
int N, K;
cin >> N >> K;
int H[N][2];
int L[N];
for (int i = 0; i + 1 < N; i++)
cin >> H[i][0] >> H[i][1] >> L[i];
printf("%d", best_path(N, K, H, L));
}*/
