#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define siz(x) (long long)(x.size())
#define all(x) x.begin(), x.end()
#define debug_arr(x,len) for(long long _=1; _<=len; _++) cout<<x[_]<<" "; cout<<'\n';
#define debug(x) cout<<'\n'<<#x<<": "<<x<<'\n';
const long long maxN = 1e6+5;
long long n, k, sz[maxN], mx_weight = 0, ans = 0, cur_min = 1e18;
long long cnt[maxN];
bool del[maxN];
vector<pair<long long,long long>>adj[maxN];
void dfs(long long u, long long v)
{
sz[u] = 1;
for(auto [i, val]: adj[u])
{
if(i == v || del[i]) continue;
dfs(i, u);
sz[u] += sz[i];
}
}
long long find_centroid(long long u, long long v, long long total)
{
for(auto [i, val]: adj[u])
{
if(i == v || del[i]) continue;
if(sz[i] > total/2) return find_centroid(i, u, total);
}
return u;
}
void update(long long u, long long v, long long weight, bool type, long long layer)
{
if(weight > k) return;
mx_weight = max(mx_weight, weight);
if(type == 1)
{
cnt[weight] = min(cnt[weight], layer);
}
else
{
long long xet = layer + cnt[k-weight];
cur_min = min(cur_min, xet);
}
for(auto [i, val]: adj[u])
{
if(i == v || del[i]) continue;
update(i, u, weight + val, type, layer+1);
}
}
void cal(long long u)
{
dfs(u, 0);
long long root = find_centroid(u, 0, sz[u]);
mx_weight = -1e18; cnt[0] = 0; del[root] = 1;
for(auto [i, val]: adj[root])
{
if(del[i]) continue;
update(i, root, val, 0, 1);
update(i, root, val, 1, 1);
}
for(long long i=0; i<=mx_weight; i+=1) cnt[i] = 1e18;
for(auto [i, val]: adj[root])
{
if(del[i]) continue;
cal(i);
}
}
// long long32_t main()
// {
// ios_base::sync_with_stdio(0); cin.tie(0);
// cin>>n>>k;
// for(long long i=1; i<=k; i+=1) cnt[i] = 1e18;
// for(long long i=1; i<n; i+=1)
// {
// long long x,y,w;
// cin>>x>>y>>w; x++; y++;
// adj[x].push_back({y,w});
// adj[y].push_back({x,w});
// // cout<<x<<" "<<y<<" "<<w<<'\n';
// }
// cal(1);
// if(cur_min == 1e18) cout<<-1<<'\n';
// else cout<<cur_min<<'\n';
// }
int best_path(int N, int K, int H[][2], int L[])
{
n = N; k = K;
for(long long i=1; i<=k; i+=1) cnt[i] = 1e18;
for(long long i=0; i<n-1; i+=1)
{
long long x,y,w;
x = H[i][0], y = H[i][1], w = L[i];
x++; y++;
adj[x].push_back({y,w});
adj[y].push_back({x,w});
// cout<<x<<" "<<y<<" "<<w<<'\n';
}
cal(1);
if(cur_min == 1e18) return -1;
else return cur_min;
}
