#include <bits/stdc++.h>
typedef long long ll;
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
ll n, k;
std::cin >> n >> k;
std::vector<std::vector<std::pair<ll, ll>>> adj(n + 1);
ll min_w = 1e15;
for (ll i = 0, u, v, w; i < n - 1; ++i) {
std::cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
min_w = std::min(min_w, w);
}
if (k < min_w) {
std::cout << n << '\n';
for (ll i = 1; i <= n; ++i) {
std::cout << i << ' ';
}
std::cout << '\n';
return 0;
}
if (n <= 17) {
std::pair<ll, ll> ans = {1e15, -1};
for (ll mask = 1; mask < (1 << n); ++mask) {
std::priority_queue<std::pair<ll, ll>> pq;
std::vector<bool> vis(n + 1);
std::vector<ll> dist(n + 1, 1e15);
dist[0] = 0;
for (ll i = 0; i < n; ++i) {
if (mask & (1 << i)) {
dist[i + 1] = 0;
pq.push({0, i + 1});
}
}
while (!pq.empty()) {
auto [d, node] = pq.top();
pq.pop();
if (vis[node]) {
continue;
}
vis[node] = true;
d *= -1;
for (auto &[ch, w] : adj[node]) {
if (d + w < dist[ch]) {
dist[ch] = d + w;
pq.push({-dist[ch], ch});
}
}
}
if (*std::max_element(dist.begin(), dist.end()) <= k) {
ans = std::min(ans, {__builtin_popcount(mask), mask});
}
}
std::cout << ans.first << '\n';
for (ll i = 0; i < n; ++i) {
if (ans.second & (1 << i)) {
std::cout << i + 1 << ' ';
}
}
std::cout << '\n';
return 0;
}
if (2 * min_w > k) {
// dp[node][0] => you need to cover parent
// dp[node][1] => parent covers you
// dp[node][2] => you only need to cover your subtree
std::vector<std::vector<ll>> dp(n + 1, std::vector<ll>(3, 1e15));
std::vector<bool> is_leaf(n + 1, true);
std::function<void(ll, ll, ll)> dfs;
dfs = [&](ll node, ll par, ll wt) {
ll sum = 0;
for (auto &[ch, w] : adj[node]) {
if (ch == par) {
continue;
}
is_leaf[node] = false;
dfs(ch, node, w);
sum += dp[ch][2];
}
if (is_leaf[node]) {
dp[node][0] = wt <= k ? 1 : 1e15;
dp[node][1] = wt <= k ? 0 : 1e15;
dp[node][2] = 1;
} else {
dp[node][0] = 1;
dp[node][1] = 0;
for (auto &[ch, w] : adj[node]) {
if (ch == par) {
continue;
}
if (w <= k) {
dp[node][2] = std::min(dp[node][2], sum - dp[ch][2] + dp[ch][0]);
dp[node][0] += dp[ch][1];
} else {
dp[node][0] += dp[ch][2];
}
dp[node][1] += dp[ch][2];
}
dp[node][1] = std::min(dp[node][1], dp[node][0]);
dp[node][2] = std::min(dp[node][2], dp[node][0]);
}
};
dfs(1, 0, 0);
std::vector<ll> ans;
std::function<void(ll, ll, ll)> build_ans;
build_ans = [&](ll node, ll par, ll j) {
if (is_leaf[node]) {
if (j == 0 or j == 2) {
ans.push_back(node);
}
return;
}
if (j == 0) {
ans.push_back(node);
for (auto &[ch, w] : adj[node]) {
if (ch == par) {
continue;
}
if (w <= k) {
build_ans(ch, node, 1);
} else {
build_ans(ch, node, 2);
}
}
} else if (j == 1) {
if (dp[node][1] == dp[node][0]) {
build_ans(node, par, 0);
return;
}
for (auto &[ch, w] : adj[node]) {
if (ch == par) {
continue;
}
build_ans(ch, node, 2);
}
} else {
if (dp[node][2] == dp[node][0]) {
build_ans(node, par, 0);
return;
}
ll sum = 0;
for (auto &[ch, w] : adj[node]) {
if (ch == par) {
continue;
}
sum += dp[ch][2];
}
bool found = false;
for (auto &[ch, w] : adj[node]) {
if (ch == par) {
continue;
}
if (!found and dp[node][2] == sum - dp[ch][2] + dp[ch][0]) {
found = true;
build_ans(ch, node, 0);
} else {
build_ans(ch, node, 2);
}
}
}
};
build_ans(1, 0, 2);
std::cout << dp[1][2] << '\n';
for (auto &i : ans) {
std::cout << i << ' ';
}
std::cout << '\n';
return 0;
}
std::set<ll> active;
for (ll i = 1; i <= n; ++i) {
active.insert(i);
}
std::function<void(ll, ll, ll)> dfs;
std::vector<std::pair<ll, ll>> up(n + 1);
std::vector<ll> depths(n + 1);
dfs = [&](ll node, ll par, ll depth) {
depths[node] = depth;
for (auto &[i, wt] : adj[node]) {
if (i == par or !active.count(i)) {
continue;
}
up[i] = {node, wt};
dfs(i, node, depth + wt);
}
};
dfs(1, 0, 0);
std::priority_queue<std::pair<ll, ll>> pq;
for (ll i = 1; i <= n; ++i) {
pq.push({depths[i], i});
}
std::vector<ll> ans;
while (!pq.empty()) {
ll deepest = pq.top().second;
pq.pop();
if (!active.count(deepest)) {
continue;
}
ll dist = 0;
while (deepest != 1 and dist + up[deepest].second <= k) {
dist += up[deepest].second;
deepest = up[deepest].first;
}
ans.push_back(deepest);
std::function<void(ll, ll, ll)> dfs2;
dfs2 = [&](ll node, ll par, ll depth) {
if (depth > k) {
return;
}
active.erase(node);
for (auto &[i, wt] : adj[node]) {
if (i == par) {
continue;
}
dfs2(i, node, depth + wt);
}
};
dfs2(deepest, 0, 0);
}
std::cout << ans.size() << '\n';
for (auto &i : ans) {
std::cout << i << ' ';
}
std::cout << '\n';
}
