마법사의 표식

고블린들은 땅속 소굴에서 지표면으로 이어지는 터널망을 가지고 있다. 그림에서 위쪽은 지표면 방향을 나타낸다. 소굴은 라벨 $A$, 지표면(출구)은 라벨 $F$이고, 나머지 라벨은 터널이 만나는 교차점을 표시한다. 어떤 교차점에서 지표면 쪽으로 올라가는 터널은 그림에서 위로 향하도록 그려져 있다. 이것은 3차원 터널망을 2차원으로 그린 개략도이므로, 라벨이 붙은 교차점이 아닌 곳에서 선이 겹쳐 보이더라도 실제로는 만나지 않는다 (예를 들어 변 $BD$와 변 $CE$는 서로 교차하지 않는다).

선한 마법사 무리는 모험 중 이런 터널을 통해 지표면까지 최소 시간으로 서둘러 올라가야 할 때가 많다. 한 교차점에서 위로 올라가는 터널이 여러 개일 수 있고, 일반적으로 어느 터널이 최선인지 한눈에 알기 어렵다. 그래서 마법사들은 터널망을 지도로 만들어, 한 교차점에서 다음 교차점까지 올라가는 데 걸리는 시간을 기록해 두었다. 급할 때는 복잡한 기록을 볼 겨를이 없고, 같은 터널을 지나갈지도 모르는 적을 돕고 싶지도 않다. 그래서 필요한 교차점에만 아주 은밀한 표식을 남기기로 했다. 교차점을 떠나는 어떤 터널에 표식이 있으면, 마법사는 그 터널을 따라가야 한다. 다만 표식이 발각될 수 있고, 특히 표식이 너무 많으면 더 그러하므로, 마법사들은 가능한 한 적은 수의 교차점에만 표식을 남기고 싶어 한다. 그러면서도 “항상 위로 올라가고, 표식이 있는 터널이 있으면 반드시 그 터널을 택한다”는 규칙을 따르는 마법사라면 누구든 최소 시간에 지표면으로 나오도록 보장해야 한다.

위에서 설명한 첫 번째 터널망을 예로 들자. 한 가지 방법은 $A$에서 $B$로, 그리고 $B$에서 $C$로 향하는 표식을 두는 것이다. $C$에서 위로 가는 길은 하나뿐이므로, 표식을 따라온 마법사는 $A \to B \to C \to F$ 경로로 나가며 총 시간은 $3 + 1 + 4 = 8$로 가능한 최소값이다.

같은 터널망에서 표식을 단 하나만 써도 된다. $E$에서 $D$로 향하는 표식 하나만 두는 경우다. 이 표식은 경로를 완전히 결정하지는 않는다. $A$에서 마법사는 $B$나 $E$ 어느 쪽으로도 갈 수 있고 $B$에서 다시 두 갈래가 있지만, 이 위쪽 경로들은 모두 같은 최소 시간 $8$을 차지한다. $E$의 표식은 없앨 수 없다. 없애면 마법사가 $A \to E \to C \to F$로 가서 $2 + 3 + 4 = 9$가 될 수 있기 때문이다. 따라서 이 터널망에서는 표식 하나로 충분하다(또 다른 한 개짜리 방법은 $A$에서 $B$로 향하는 표식을 두는 것이다).

마법사들이 표식 배치를 계획하도록 도와라. 알고리즘에 주의하라. 자칫 시간이 매우 오래 걸릴 수 있다.

입력은 1개 이상 16개 이하의 데이터 집합으로 이루어지며, 마지막에 $0$ 하나만 있는 줄이 온다.

각 데이터 집합의 첫 줄에는 정수 $n$ ($2 \le n \le 17$)이 주어진다. 이는 라벨이 붙은 지점의 수로, 출발점, 도착점, 그리고 그 사이의 교차점들을 모두 포함한다.

이어지는 $n$개의 줄은 각각 한 지점에서 위로 올라가는 터널들을 설명한다. 각 줄은 같은 형식이며 공백으로 구분된다. 먼저 그 터널의 출발 지점을 나타내는 문자가 오고, 이어서 그 지점에서 위로 올라가는 터널의 개수 $u$가 온다. 그 뒤에는 (문자, 시간) 쌍이 $u$개 오는데, 각 쌍은 현재 지점에서 라벨이 그 문자인 지점으로 가는 터널의 통과 시간 $time$ ($1 \le time \le 500$)을 나타낸다. $n$개 줄 맨 앞의 라벨은 대문자 알파벳의 처음부터 순서대로 붙는다. $A$는 항상 출발점이고, 사용된 마지막 문자는 항상 출구다. 오직 마지막 줄(출구)만 $u = 0$을 가진다. 그 앞의 줄들은 $1 \le u \le 6$을 만족한다.

제약 조건:

• 마법사는 어떤 교차점에서도 위로 올라가는 터널만 따라갈 수 있다.
• 터널의 총 개수는 최대 35개다.
• 최소 시간으로 소굴에서 지표면까지 가는 경로가 항상 존재하며, 그 경로는 터널을 최대 7개 지난다.
• 출발점과 출구를 제외한 모든 지점은, 그 지점으로 올라오는 터널이 적어도 하나, 그 지점에서 올라가는 터널이 적어도 하나 있다.

예시 입력의 첫 번째 데이터 집합은 위에서 설명한 터널망에 해당한다.

각 데이터 집합마다 한 줄씩, 공백으로 구분된 두 수를 출력한다. 소굴에서 지표면까지 가는 최소 시간과, 모든 마법사가 그 최소 시간으로 이동하도록 보장하는 데 필요한 표식의 최소 개수다.