#include <bits/stdc++.h>
using namespace std;
constexpr int INF = 1e9;
vector<vector<pair<int, int>>> adj;
int n, k;
vector<int> best;
vector<int> temp;
vector<int> to_undo;
vector<int> to_undo2;
vector<int> sz;
vector<bool> visited;
int ans = INF;
int get_sz(int node, int par)
{
sz[node] = 1;
for (auto i : adj[node])
{
if (visited[i.first] || i.first == par) continue;
sz[node] += get_sz(i.first, node);
}
return sz[node];
}
int get_centroid(int node, int par, int sub_sz)
{
for (auto i : adj[node])
{
if (visited[i.first] || i.first == par) continue;
if (sz[i.first] * 2 > sub_sz) return get_centroid(i.first, node, sub_sz);
}
return node;
}
void dfs(int node, int par, int dist, int depth)
{
if (dist > k) return;
temp[dist] = min(temp[dist], depth);
to_undo.emplace_back(dist);
for (auto i : adj[node])
{
if (visited[i.first] || i.first == par) continue;
dfs(i.first, node, dist + i.second, depth + 1);
}
}
void get_centroid_decomp(int node)
{
int centroid = get_centroid(node, -1, get_sz(node, -1));
best[0] = 0;
for (auto i : adj[centroid])
{
if (visited[i.first]) continue;
dfs(i.first, centroid, i.second, 1);
for (auto j : to_undo)
{
if (best[k - j] == INF) continue;
ans = min(ans, temp[j] + best[k - j]);
}
for (auto j : to_undo) best[j] = min(best[j], temp[j]);
for (auto i : to_undo) to_undo2.emplace_back(i);
for (auto i : to_undo) temp[i] = INF;
to_undo.clear();
}
for (auto i : to_undo2) best[i] = INF;
visited[centroid] = true;
for (auto i : adj[centroid])
{
if (visited[i.first]) continue;
get_centroid_decomp(i.first);
}
}
int best_path(int N, int K, vector<vector<int>> H, vector<int> L)
{
n = N, k = K;
adj.resize(n);
for (int j = 0; j < N - 1; j++)
{
auto i = H[j];
adj[i[0] - 1].emplace_back(i[1] - 1, L[j]);
adj[i[1] - 1].emplace_back(i[0] - 1, L[j]);
}
best.resize(k + 1, INF);
temp.resize(k + 1, INF);
sz.resize(n);
visited.resize(n);
get_centroid_decomp(0);
if (ans == INF) return -1;
return ans;
}
/*
int main()
{
int a, b;
cin >> a >> b;
vector<vector<int>> zw(a - 1, vector<int>(2));
vector<int> l(a - 1);
for (int i = 0; i < a - 1; i++)
{
int x, y, w;
cin >> x >> y >> w;
zw[i][0] = x; zw[i][1] = y;
l[i] = w;
}
cout << best_path(a, b, zw, l);
}
*/
