#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
//#define endl '\n'
typedef pair<int,int> pii;
const int N=200010;
const int K=1000010;
struct Node
{
int c, d, q;
};
int n, k;
vector<pii> grafo[N];
int sub[N];
int pc[N];
vector<Node> values;
pii best[K][2];
int dfsCent(int u, int p)
{
sub[u] = 1;
for(auto [v,w] : grafo[u])
{
if(v==p || pc[v]) continue;
sub[u] += dfsCent(v, u);
}
return sub[u];
}
int findCent(int u, int p, int q)
{
for(auto [v,w] : grafo[u])
{
if(v==p || pc[v]) continue;
if((2*sub[v])>q) return findCent(v, u, q);
}
return u;
}
int findCent(int u)
{
return findCent(u, u, dfsCent(u, u));
}
void dfsCalc(int u, int p, int wp, int d, int q, int c)
{
d += wp;
q++;
if(k<d) return;
values.pb({c,d,q});
for(auto [v,w] : grafo[u])
{
if(v==p || pc[v]) continue;
dfsCalc(v, u, w, d, q, c);
}
return;
}
void Change(int d, pii novo)
{
for(int i = 0;i < 2;i++)
{
if(best[d][i].se!=novo.se) continue;
best[d][i] = min(best[d][i], novo);
if(best[d][0].fi>best[d][1].fi) swap(best[d][0], best[d][1]);
return;
}
best[d][1] = min(best[d][1], novo);
if(best[d][0].fi>best[d][1].fi) swap(best[d][0], best[d][1]);
return;
}
int Calc(int u)
{
int ans = N;
int q = 0;
for(auto [v,w] : grafo[u])
{
if(pc[v]) continue;
q++;
dfsCalc(v, u, w, 0, 0, v);
}
values.pb({u,0,0});
for(auto [c,d,q] : values) Change(d,{q,c});
for(auto [c,d,q] : values)
{
int nd = k-d;
if(c!=best[nd][0].se) ans = min(ans, best[nd][0].fi+q);
else ans = min(ans, best[nd][1].fi+q);
}
for(auto [c,d,q] : values) best[d][0] = best[d][1] = {N,-1};
values.clear();
return ans;
}
int Solv(int u, int p)
{
int c = findCent(u);
pc[c] = p;
int ans = Calc(c);
for(auto [v,w] : grafo[c])
{
if(pc[v]) continue;
ans = min(ans, Solv(v, c));
}
return ans;
}
int best_path(int auxN, int auxK, int edges[][2], int len[])
{
n = auxN;
k = auxK;
for(int i = 0;i < n-1;i++)
{
int u = edges[i][0]+1;
int v = edges[i][1]+1;
int w = len[i];
grafo[u].pb({v,w});
grafo[v].pb({u,w});
}
for(int i = 0;i <= k;i++) best[i][0] = best[i][1] = {N,-1};
int ans = Solv(1, -1);
if(ans==N) ans = -1;
return ans;
}
// int32_t main()
// {
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
// int n, k;
// cin >> n >> k;
// int h[n-1][2];
// int l[n-1];
// for(int i = 0;i < n-1;i++) cin >> h[i][0] >> h[i][1] >> l[i];
// cout << best_path(n, k, h, l) << endl;
// return 0;
// }
