#include<bits/stdc++.h>
#include<race.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pli pair<ll, int>
#define f first
#define s second
int sol = 1e9;
void dfs(vector<vector<pii>> &graph, vector<int> &sub, int i, int p)
{
sub[i]=1;
for (pii ele:graph[i])
{
if (ele.f == p) continue;
dfs(graph, sub, ele.f, i);
sub[i] += sub[ele.f];
}
}
int centroid(vector<vector<pii>> &graph, vector<int> &sub, int i, int p, int n)
{
for (pii ele:graph[i])
{
if (ele.f == p) continue;
if (sub[ele.f]*2 > n) return centroid (graph, sub, ele.f, i, n);
}
return i;
}
void finde(vector<vector<pii>> &graph, vector<pli> &dist, vector<int> &nodes, int i, int p, ll d, int di)
{
di++;
dist.push_back({d, di});
nodes.push_back(i);
for (pii ele:graph[i])
{
if (ele.f == p) continue;
finde(graph, dist, nodes, ele.f, i, d+ele.s, di);
}
}
void cd(vector<vector<pii>> &graph, int K)
{
int n = graph.size();
vector<int> sub(n, 0);
dfs(graph, sub, 0, -1);
int c = centroid(graph, sub, 0, -1, n);
map<ll, int> paths;
paths[0] = 1;
vector<int> nind(n, 0);
for (pii ele:graph[c])
{
vector<pli> dist;
vector<int> nodes;
finde(graph, dist, nodes, ele.f, c, ele.s, 1);
for (pli d:dist)
{
if (d.first > K) continue;
if (paths[K-d.first]==0) continue;
sol = min(paths[K-d.first]+d.second, sol);
}
for (pli d:dist)
{
if (paths[d.first]==0) paths[d.first] = d.second;
else paths[d.first] = min(paths[d.first], d.second);
}
for (int i = 0; i < nodes.size(); i++) nind[nodes[i]] = i;
vector<vector<pii>> graph2(nodes.size());
for (int node:nodes)
{
for (pii conn:graph[node])
{
if (conn.f==c) continue;
graph2[nind[node]].push_back({nind[conn.first], conn.second});
}
}
cd(graph2, K);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
vector<vector<pii>> graph(N);
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]});
}
cd(graph, K);
return sol-2;
}
/*
int32_t main()
{
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
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);
return 0;
}
*/
