Tree Partition

You are given a tree with N vertices and N-1 weighted edges. You are also given a positive integer K, where K is smaller than N.

Choose exactly K vertices. The first graph is formed from those chosen vertices and only the original tree edges whose two endpoints are both chosen. The second graph is formed from the remaining N-K vertices and only the original tree edges whose two endpoints are both unchosen. Edges connecting a chosen vertex to an unchosen vertex are included in neither graph.

For instance, in the tree with 7 vertices shown in <Figure 1>, choosing vertices 1 and 2 creates the graph in <Figure 2> (A), and the remaining vertices create the graph in <Figure 2> (B).

If vertices 3 and 4 are chosen from the tree in <Figure 1>, the two graphs are formed as shown in <Figure 3> (A) and (B).

In the two graphs of <Figure 2>, the sum of all included edge weights is 10+20+10+25=65. In the two graphs of <Figure 3>, that sum is 10.

Given the tree and K, find the minimum possible sum of the weights of all edges included in the two graphs formed by choosing K vertices in this way.

The first line contains N and K separated by a space. The vertices of the tree are numbered from 1 to N.

Each of the next N-1 lines describes one edge. Each line contains the two endpoint vertex numbers and the edge weight, separated by spaces.

N is a positive integer at most 1,000, K is a positive integer smaller than N, and every edge weight is a positive integer at most 1,000.

On the first line, print the minimum possible sum of the weights of all edges included in the two graphs formed after choosing K vertices.

On the second line, print the numbers of the chosen K vertices in increasing order, separated by spaces. If there is more than one optimal choice, print any one of them.