题目描述

译自 COCI 2021/2022 Contest #4 T4「Parkovi」

城镇的管理者决定通过修建公园来美化景观。为了让公园不仅看上去好看，并且实用，他们需要认真地选择把公园修建在哪些社区中，才能使其他社区的孩子们有至少一个公园离他们较近。

这个镇有 $n$ 个社区，社区由 $n-1$ 条长度确定的道路连接。从任意一个社区出发都有唯一的道路与另一个任意社区连接。换句话说，社区和道路组成了一棵树。在不同的社区中需要恰好修建 $k$ 个公园，使得其他社区到离它最近的公园尽可能近。更准确地说，管理员想要最小化从某个社区到离它最近的公园的最大距离。

请帮助城镇管理者确定哪些社区应该修建公园，并确定某个社区到离它最近公园的最大距离。

输入格式

第一行包含两个正整数 $n,k$，分别表示社区和公园的总数。

接下来 $n-1$ 行，每行三个整数 $a_i,b_i,w_i$，表示一条连接社区 $a_i$ 和 $b_i$ 的路，长度为 $w_i$。

输出格式

第一行输出某个社区到离它最近公园的最大距离的可能最小值。

第二行输出 $k$ 个整数，输出需要修建公园的社区编号。如果有多于一组解，输出任意一组即可。

9 3
1 2 5
1 3 1
3 4 10
3 5 9
5 6 8
2 7 1
2 8 2
8 9 7

8
4 5 8

5 2
1 2 3
2 3 7
3 4 3
4 5 3

3
2 4

7 4
1 3 1
1 4 1
2 3 1
5 3 1
4 7 1
4 6 1

1
3 4 1 2

数据范围与提示

对于全部数据，$1\le k\le n\le 2\times 10^5,1\le a_i,b_i\le n,1\le w_i\le 10^9$。

详细子任务附加限制及分值如下表所示：