#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define ll long long
const int mod = 1e9 + 7;
const int mxN = 5e5 + 5;
#define MAX_N 500000
vector<vector<pair<int,int>>>v;
map<int,int>mp[mxN];
int vis[mxN];
int n, k;
int sh[mxN],sha[mxN];
int ans;
int p[mxN];
void dfs(int u){
vis[u] = 1;
for(auto ch : v[u]){
if(!vis[ch.F]){
dfs(ch.F);
int a = u,b = ch.F;
if(mp[p[a]].size() < mp[p[b]].size()){
swap(a,b);
}
if(b == u){
for(auto x : mp[p[b]]) {
if(mp[p[a]][k - x.first - sh[p[b]] - sh[p[a]] - ch.S] + sha[p[a]])
ans = min(ans, x.second + sha[p[b]] + mp[p[a]][k - x.first - sh[p[b]] - sh[p[a]] - ch.S] + sha[p[a]] + 1);
}
for(auto x : mp[p[b]]){
if(mp[p[a]][x.first - ch.S + sh[p[b]] - sh[p[a]]])
mp[p[a]][x.first - ch.S + sh[p[b]] - sh[p[a]]] = min(mp[p[a]][x.first - ch.S + sh[p[b]] - sh[p[a]]],x.second - 1 + sha[p[b]]);
else mp[p[a]][x.first - ch.S + sh[p[b]] - sh[p[a]]] = x.second - 1 + sha[p[b]];
}
sh[p[a]] += ch.S;
sha[p[a]]++;
}else{
for(auto x : mp[p[b]]) {
if(mp[p[a]][k - x.first - sh[p[b]] - sh[p[a]] - ch.S] + sha[p[a]])
ans = min(ans, x.second + sha[p[b]] + mp[p[a]][k - x.first - sh[p[b]] - sh[p[a]] - ch.S] + sha[p[a]] + 1);
}
for(auto x : mp[p[b]]){
if(mp[p[a]][x.first + ch.S + sh[p[b]] - sh[p[a]]])
mp[p[a]][x.first + ch.S + sh[p[b]] - sh[p[a]]] = min(mp[p[a]][x.first + ch.S + sh[p[b]] - sh[p[a]]],x.second + 1 + sha[p[b]]);
else mp[p[a]][x.first + ch.S + sh[p[b]] - sh[p[a]]] = x.second + 1 + sha[p[b]];
}
}
p[b] = p[a];
}
}
mp[p[u]][-sh[p[u]]] = 0;
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N;k = K;
ans = 2e9;
memset(vis,0,sizeof vis);
for(int i = 1;i <= n;i++){
p[i] = i;
sh[i] = 0;
mp[i].clear();
}
v.clear();
v.resize(n + 1);
for (int i = 0;i < n - 1;i++){
v[H[i][0] + 1].push_back({H[i][1] + 1,L[i]});
v[H[i][1] + 1].push_back({H[i][0] + 1,L[i]});
}
dfs(1);
if(ans == 2e9) ans = -1;
return ans;
}
//
// static int N, K;
// static int H[MAX_N][2];
// static int L[MAX_N];
// static int solution;
// 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]));
// }
//
// main()
// {
// read_input();
// best_path(N,K,H,L);
// cout<<ans;
// return 0;
// }
