Background

The city government decided to build parks to beautify the scenery. To make the parks not only look good but also be useful, the city government hopes that residents in the parks can be closer to each other, for the happiness of the citizens.

Problem Description

This city consists of $n$ communities, connected by $n-1$ roads. From any community, you can reach any other community. A total of $k$ parks will be built, and there will be at most one park in each community. The city government wants to minimize the maximum value of the distance from each community to its nearest park as much as possible.

Help the government decide in which communities to build parks, so that the maximum distance from every community to its nearest park is minimized.

Input Format

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

The next $n-1$ lines describe the roads. The $i$-th line contains three numbers $a_i,b_i,w_i$, meaning there is a road of length $w_i$ connecting communities $a_i$ and $b_i$.

Output Format

The first line contains one integer, which is the minimum possible value of the maximum distance from each community to its nearest park.

The second line contains $k$ integers, the community indices where parks should be built to minimize the maximum distance from each community to its nearest park.

If there are multiple solutions, output any one.

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

Hint

[Explanation for Sample 3]

If parks are built only in communities $3$ and $4$, the maximum distance will not change. However, the government wants to build $k$ parks, so it needs to build two more in other places.

[Constraints and Notes]

This problem uses bundled subtasks.

• Subtask 1 (10 pts): $1 \le n \le 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 testdata, $1\le k\le n\le2\times10^5,1\le a_i,b_i\le n,1\le w_i \le 1e9$.

[Hints and Additional Information]

The score of this problem follows the original COCI problem setting, with a full score of $110$.

Translated from T4 Parkovi of COCI2021-2022 CONTEST #4.

Translated by ChatGPT 5