#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxN = 20010;
vector<pair<int, int>> graph[maxN];
vector<bool> is_removed(maxN, 0);
vector<int> subtree_size(maxN, 0);
vector<int> pathsize(maxN, 0);
vector<int> depth(maxN, 0);
int ans = 1e9;
int k;
// #define MAX_N 500000
// static int N, K;
// static int H[MAX_N][2];
// static int L[MAX_N];
// static int solution;
int get_subtree_size(int node, int parent = -1) {
subtree_size[node] = 1;
for (auto child : graph[node]) {
if (child.first == parent || is_removed[child.first]) { continue; }
subtree_size[node] += get_subtree_size(child.first, node);
}
return subtree_size[node];
}
int get_centroid(int node, int tree_size, int parent = -1) {
for (auto child : graph[node]) {
if (child.first == parent || is_removed[child.first]) { continue; }
if (subtree_size[child.first] * 2 > tree_size) {
return get_centroid(child.first, tree_size, node);
}
}
return node;
}
void dfs(int v, int parent, map<int, int> &m){
for(auto u: graph[v]){
if(u.first!= parent && !is_removed[u.first]){
//cout<<u.first<<" ";
pathsize[u.first] = pathsize[v] + u.second;
depth[u.first] = depth[v] +1;
if(m.find(pathsize[u.first]) == m.end()) m[pathsize[u.first]] = depth[u.first];
else m[pathsize[u.first]] = min(depth[u.first], m[pathsize[u.first]]);
dfs(u.first, v, m);
}
}
}
/** Build up the centroid decomposition recursively */
void build_centroid_decomp(int node = 0) {
int centroid = get_centroid(node, get_subtree_size(node));
//cout<<centroid<<" -> "<<"\n";
// do something
map<int, vector<pair<int, int>> > pathlist;
for(auto child : graph[centroid]){
if(!is_removed[child.first]){
map<int, int> m;
depth[child.first] = 1;
pathsize[child.first] = child.second;
m[pathsize[child.first]] = depth[child.first];
dfs(child.first, centroid, m);
//cout<<"x\n";
for(auto p: m){
pathlist[p.first].push_back({p.second,child.first});
}
}
}
auto it = pathlist.begin();
for(; it != pathlist.end(); it++){
sort((*it).second.begin(), (*it).second.end());
}
for(auto p: pathlist){
int vertice = (p.second)[0].second;
int length = (p.second)[0].first;
//cout<<vertice<<" "<<length<<"\n";
if(pathlist.find(k - p.first) != pathlist.end()){
int nextvertice = pathlist[k - p.first][0].second;
int nextlength = pathlist[k - p.first][0].first;
if(vertice == nextvertice){
if(pathlist[k-p.first].size() == 1) continue;
nextvertice = pathlist[k - p.first][1].second;
nextlength = pathlist[k - p.first][1].first;
}
ans = min(ans, length + nextlength);
}
}
if(pathlist.find(k) != pathlist.end()){
ans = min(ans, pathlist[k][0].first);
}
is_removed[centroid] = true;
for (auto child : graph[centroid]) {
if (is_removed[child.first]) { continue; }
build_centroid_decomp(child.first);
}
}
// void solve(){
// int n; cin>>n>>k;
// for(int i = 1; i<n; i++){
// int u,v,w ;
// cin>>u>>v>>w;
// graph[u].push_back({v, w});
// graph[v].push_back({u, w});
// }
// build_centroid_decomp(0);
// //cout<<ans<<"\n";
// printf("%lld\n", ans);
// }
int best_path(int N, int K, int h[][2], int L[]){
ans = 1e9;
int n = N;
k = K;
for(int i = 0; i<n-1; i++){
graph[h[i][0]].push_back({h[i][1], L[i]});
graph[h[i][1]].push_back({h[i][0], L[i]});
}
build_centroid_decomp(0);
if(ans > 1e8) ans = -1;
return ans;
}
// inline
// void my_assert(int e) {if (!e) abort();}
// void read_input(){
// int i;
// my_assert(2==scanf("%d %d",&N,&K));
// for(i=0; i<N-1; i++)
// my_assert(3==scanf("%d %d %d",&H[i][0],&H[i][1],&L[i]));
// my_assert(1==scanf("%d",&solution));
// }
// int main(){
// int ans;
// read_input();
// ans = best_path(N,K,H,L);
// if(ans==solution)
// printf("Correct.\n");
// else
// printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);
// return 0;
// }
// signed main(){
// // ios_base::sync_with_stdio(false);
// // cin.tie(NULL);
// // cout.tie(NULL);
// int t=1; //cin>>t;
// while(t--){
// solve();
// }
// }
