/*input
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
*/
#include<bits/stdc++.h>
#include "race.h"
using namespace std;
const int N=2e5 + 100;
const int mod=1e9 + 7;
const int inf=1e7;
#define pii pair<int, int>
#define f first
#define s second
#define mp make_pair
//Trace prints the name of the variable and the value.
int k, n;vector< pii > adjlist[N];
queue<int> roots;bool cent[N];
class Cent
{
bool visited[N];
int sum[N];stack<int> cvals;
void dfs(int i)
{
sum[i]=1;visited[i]=1;
for(auto j:adjlist[i])
{
if(visited[j.f]||cent[j.f]) continue;
dfs(j.f);sum[i]+=sum[j.f];
}
cvals.push(i);
}
public:
void init() {
for(int i=1;i<=n;i++) {visited[i]=0;sum[i]=0;}
}
bool solve()
{
init();bool check=0;
for(int i=1;i<=n;i++)
{
if(visited[i]||cent[i]) continue;check=1;
dfs(i);int tot=sum[cvals.top()];int cr, mval=inf;
while(!cvals.empty())
{
int cmax=tot-sum[cvals.top()];
for(auto j:adjlist[cvals.top()])
{
if(sum[j.f]>sum[cvals.top()]||cent[j.f]) continue;
cmax=max(cmax, sum[j.f]);
}
if(cmax<mval)
{
mval=cmax;cr=cvals.top();
}
cvals.pop();
}
roots.push(cr);cent[cr]=1;
}
return check;
}
};
int tally[N*5];int optans;
void query(int i, int p, int depth, int dist)
{
if(dist>k) return;
if(tally[k-dist]!=inf)
{
optans=min(optans, tally[k-dist] + depth);
}
for(auto j:adjlist[i])
{
if(cent[j.f]||j.f==p) continue;
query(j.f, i, depth+1, dist+j.s);
}
}
void update(int i, int p, int depth, int dist, int ind)
{
if(dist>k) return;
if(ind==0) tally[dist]=min(tally[dist], depth);
else tally[dist]=inf;
for(auto j:adjlist[i])
{
if(cent[j.f]||j.f==p) continue;
update(j.f, i, depth+1, dist+j.s, ind);
}
}
Cent obj;
int best_path(int NC, int K, int H[][2], int L[])
{
n=NC;k=K;optans=inf;
for(int i=0;i<=k;i++) tally[i]=inf;
for(int i=1;i<=n;i++) cent[i]=0;
for(int i=0;i<n-1;i++)
{
adjlist[H[i][0]+1].push_back(mp(H[i][1]+1, L[i]));adjlist[H[i][1]+1].push_back(mp(H[i][0]+1, L[i]));
}
tally[0]=0;int iter=0;
while(obj.solve())
{
while(!roots.empty())
{
int cur=roots.front();
for(auto j:adjlist[cur])
{
if(cent[j.f]) continue;
query(j.f, cur, 1, j.s);update(j.f, cur, 1, j.s, 0);
}
for(auto j:adjlist[cur])
{
if(cent[j.f]) continue;
update(j.f, cur, 1, j.s, 1);
}
roots.pop();
}
}
if(optans==inf) return -1;return optans;
}
/*signed main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int NC, K, H[N][2], L[N];
cin>>NC>>K;
for(int i=0;i<NC-1;i++)
{
cin>>H[i][0]>>H[i][1]>>L[i];
}
cout<<best_path(NC, K, H, L);
}*/
