정글 도로

라그리샨(Lagrishan)이라는 열대 섬의 원로회 의장에게 고민이 있다. 몇 년 전 갑작스럽게 들어온 해외 원조금으로 마을들 사이에 여러 도로를 추가로 건설했다. 하지만 정글이 끊임없이 도로를 뒤덮기 때문에, 이 거대한 도로망을 유지하는 데 드는 비용이 너무 크다. 원로회는 일부 도로의 유지를 중단하기로 결정해야 한다.

물론 유지되는 도로만으로도 모든 마을 사이를 오갈 수 있어야 한다. 설령 예전만큼 짧은 경로가 아니더라도 말이다. 의장은 모든 마을을 연결하는 도로망을 유지하는 데 드는 최소 월 유지비(단위: aacms)가 얼마인지 원로들에게 알려주고자 한다.

마을은 A부터 시작하는 알파벳 대문자로 표시된다. 위 지도에는 현재 사용 중인 모든 도로와 각 도로의 월 유지비(aacms)가 나와 있으며, 모든 마을을 연결한 채 가장 저렴하게 유지할 수 있는 도로망의 비용은 월 216 aacms이다. 이러한 문제를 푸는 프로그램을 작성하여라.

입력은 1개 이상 100개 이하의 데이터 세트로 이루어지며, 마지막 줄에는 0만 주어진다.

각 데이터 세트는 마을의 수 $n$ 하나만 있는 줄로 시작한다($1 < n < 27$). 마을은 알파벳의 처음 $n$개 글자를 대문자로 사용해 표시한다.

이어서 $n-1$개의 줄이 주어지며, 각 줄은 알파벳 순서대로 마을 표시 문자로 시작한다(마지막 마을에 대한 줄은 없다). 각 줄은 마을 표시 문자 다음에, 그 마을에서 알파벳상 더 뒤에 있는 마을로 향하는 도로의 개수 $k$가 온다. $k$가 0보다 크면, 이어서 $k$개의 도로 정보가 주어진다. 각 도로 정보는 반대쪽 끝 마을의 표시 문자와 그 도로의 월 유지비(aacms)로 이루어진다. 유지비는 100 미만의 양의 정수이다. 한 줄의 모든 데이터는 공백 하나로 구분된다.

도로망은 항상 모든 마을 사이를 오갈 수 있도록 연결되어 있다. 도로의 총 개수는 75개를 넘지 않는다. 한 마을에서 다른 마을로 향하는 도로(알파벳상 앞이든 뒤든)는 15개를 넘지 않는다.

각 데이터 세트마다 한 줄에 정수 하나를 출력한다: 모든 마을을 연결하는 도로망을 유지하는 데 드는 최소 월 유지비(aacms).

주의: 가능한 모든 도로 집합을 검사하는 완전 탐색으로는 시간 제한 안에 끝낼 수 없다.