문제
간선의 가중치가 음수가 아닌 무방향 트리가 주어진다. 하나의 노드는 루트로 주어지며 나머지 노드는 루트로 가는 경로가 유일하다. 루트가 아니면서 자식이 없는 노드는 잎 노드이다.
루트로부터 연결된 간선들 중 일부를 잘라내어 주어진 트리의 모든 잎 노드를 제거하려고 한다. 이때 잘려지는 간선들의 가중치 합이 최소가 되도록 하고 싶다. 이를 구하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스를 포함한다. 각 테스트 케이스의 첫 행은 노드의 개수 N ( 1≤N≤1000) 과 루트가 되는 노드의 번호 R ( 1≤R≤N ) 이 주어진다. 다음 N-1 개의 행에는 노드간의 연결 정보 Ui, Vi( 1≤Ui, Vi≤N), Wi( 0≤Wi≤1000) 가 공백을 구분하여 주어진다. 중복된 간선 정보는 주어지지 않는다. 입력의 끝은 0 0 이다.
출력
각 테스트 케이스에 대하여 트리의 임의의 잎 노드로부터 루트까지 경로가 없도록 모든 잎 노드들을 제거하는데 드는 최소비용의 합을 행으로 구분하여 출력하시오.
예제1
입력
1515
121
232
253
567
465
674
5156
151011
10135
13144
12133
9108
892
9113
00
출력
16