#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 200010;
vector<pair<int, int>> graph[N];
vector<bool> is_removed(N, 0);
vector<int> subtree_size(N, 0);
vector<int> pathsize(N, 0);
vector<int> depth(N, 0);
int ans = 1e9;
int k;
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]){
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]]);
}
}
}
/** Build up the centroid decomposition recursively */
void build_centroid_decomp(int node = 0) {
int centroid = get_centroid(node, get_subtree_size(node));
// do something
pathsize[centroid] = 0;
map<int, vector<pair<int, int>> > pathlist;
//cout<<centroid<<" : \n";
for(auto child : graph[centroid]){
map<int, int> m;
dfs(child.first, -1, m);
for(auto p: m){
//cout<<p.first<<" "<<p.second<<"\n";
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;
if(pathlist.find(k - length) != pathlist.end()){
int nextvertice = pathlist[k - length][0].second;
int nextlength = pathlist[k - length][0].first;
if(vertice == nextvertice){
if(pathlist[k-length].size() == 1) continue;
nextvertice = pathlist[k - length][1].second;
nextlength = pathlist[k - length][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;
}
// signed main(){
// // ios_base::sync_with_stdio(false);
// // cin.tie(NULL);
// // cout.tie(NULL);
// int t=1; //cin>>t;
// while(t--){
// solve();
// }
// }
