간선의 가중치가 음수가 아닌 무방향 트리가 주어진다. 하나의 노드는 루트로 주어지며 나머지 노드는 루트로 가는 경로가 유일하다. 루트가 아니면서 자식이 없는 노드는 잎 노드이다.

루트로부터 연결된 간선들 중 일부를 잘라내어 주어진 트리의 모든 잎 노드를 제거하려고 한다. 이때 잘려지는 간선들의 가중치 합이 최소가 되도록 하고 싶다. 이를 구하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스를 포함한다. 각 테스트 케이스의 첫 행은 노드의 개수 N ( 1≤N≤1000) 과 루트가 되는 노드의 번호 R ( 1≤R≤N ) 이 주어진다. 다음 N-1 개의 행에는 노드간의 연결 정보 Ui, Vi( 1≤Ui, Vi≤N), Wi( 0≤Wi≤1000) 가 공백을 구분하여 주어진다. 중복된 간선 정보는 주어지지 않는다. 입력의 끝은 0 0 이다.

각 테스트 케이스에 대하여 트리의 임의의 잎 노드로부터 루트까지 경로가 없도록 모든 잎 노드들을 제거하는데 드는 최소비용의 합을 행으로 구분하여 출력하시오.