Problem Background

The city government has decided to build parks to beautify the landscape. To ensure that the parks are not only aesthetically pleasing but also functional, the government aims to bring residents closer together for the sake of their happiness.

Problem Description

The city consists of $n$ communities connected by $n-1$ roads. It is guaranteed that any community can reach any other community via these roads. A total of $k$ parks will be built, with only one park per community. The government wishes to minimize the maximum distance from any community to the nearest park.

Help the government determine which communities should have parks built in them to minimize the maximum distance from any community to the nearest park.

Input Format

The first line contains two integers $n$ and $k$, representing the number of communities and the number of parks to be built, respectively.

The next $n-1$ lines each contain three integers $a_i$, $b_i$, and $w_i$, indicating that there is a road of length $w_i$ connecting communities $a_i$ and $b_i$.

Output Format

The first line should contain a single integer, which is the minimum value of the maximum distance from any community to the nearest park.

The second line should contain $k$ integers, representing the community numbers where the parks should be built to achieve the minimum maximum distance.

If there are multiple solutions, output any one of them.

Sample Input and Output

Sample Input #1

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

Sample Output #1

8
4 5 8

Sample Input #2

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

Sample Output #2

3
2 4

Sample Input #3

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

Sample Output #3

1
3 4 1 2

Notes

[Sample 3 Explanation]

If parks are only built in communities $3$ and $4$, the maximum distance does not change. However, since the government wants to build $k$ parks, two more parks need to be built elsewhere.

[Data Range and Constraints]

This problem is tested with subtask binding.

• Subtask 1 (10 pts): $1 ≤ n ≤ 20$.
• Subtask 2 (10 pts): $k=1$.
• Subtask 3 (30 pts): $\forall i\in\{1,2,3,\dots,n-1\},a_i=i,b_i=i+1$.
• Subtask 4 (60 pts): No additional constraints.

For $100\%$ of the data, $1\le k\le n\le2\times10^5,1\le a_i,b_i\le n,1\le w_i \le 1e9$.

[Score and Origin]

This problem's score is set according to the original COCI contest, with a full score of $110$.

The problem is translated from COCI2021-2022 CONTEST #4 T4 Parkovi.

见题面 Input 部分

见题面 Output 部分