문제
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개의 정점을 선택하는 방법이 둘 이상인 경우 그 중 한 경우만 출력한다.
예제1
72
1210
1315
1430
5320
6310
4725
10
34