시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 79 17 13 18.310%

문제

N개의 정점과 이들 사이에 가중치를 갖는 간선으로 이루어진 트리가 있다. 주어진 자연수 K(K<N)에 대해, 주어진 트리에서 K개의 정점을 선택하여 그 정점과 이들 사이에 이어진 간선으로 하나의 그래프를 만들고, 나머지 N-K개의 정점과 그들 사이에 이어진 간선으로 또 하나의 그래프를 만들려고 한다.

예를 들어 <그림 1>과 같이 7개의 정점으로 이루어진 트리에서 1번, 2번 정점을 선택하여 그래프를 만들려면 <그림 2>의 (A)와 같이 되고, 나머지 정점들로 그래프를 만들면 <그림 2>의 (B)와 같이 된다.

또한 <그림 1>의 트리에서 3번, 4번 정점을 선택한 경우 마찬가지로 <그림 3>의 (A),(B)와 같이 두 그래프가 만들어진다.

<그림 2>의 두 그래프에서 모든 간선의 가중치의 합은 10+20+10+25=65가 되고<그림 3>의 두 그래프에서 모든 간선의 가충치의 합은 10이된다.

트리에 대한 정보와 K가 주어질 때, K개의 정점을 선택하여 위와 같은 방법으로 만들어진 두 그래프에 있는 모든 간선의 가중치 합의 최소값을 구하는 프로그램을 작성하시오.

입력

첫째 중에는 N과 K가 빈 칸을 사이에 두고 차례로 주어진다. 트리의 정점에는 1번부터 N번까지 번호가 매겨진다. 이어 둘째 줄부터 N-1개의 각 줄에는 간선 하나의 정보가 주어진다. 간선의 정보는 양 끝 정점 번호와 가중치가 빈 칸을 사이에 두고 차례대도 주어진다. N은 1,000이하의 자연수, K는 N보다 작은 자연수이고 간선의 가중치는 1,000이하의 자연수 이다.

출력

첫째 줄에 K개 정점을 선택하여 만들어진 두 개의 그래프에 있는 모든 간선의 가중치 합의 최소값을 출력하고, 둘째 줄에 그 때 선택한 K개 정점들의 번호를 오름차순으로 빈 칸을 사이에 두고 한 줄에 출력한다. K개의 정점을 선택하는 방법이 둘 이상인 경우 그 중 한 경우만 출력한다.

예제 입력

7 2
1 2 10
1 3 15
1 4 30
5 3 20
6 3 10
4 7 2

예제 출력

10
3 4

힌트