题目描述

令人头大的热带岛屿Lagrishan有一个难题。额外的外国援助资金花在几年前道路之间的村庄。

但丛林超过道路无情,所以大道路网络维护成本太高。长老理事会必须选择停止维护一些道路。

上面的地图显示了所有使用的道路现在成本在aacms每月维护他们。当然需要有办法让所有的村庄之间维护道路,即使不是和以前一样短的路线。

首席长老想告诉议会的长老是什么他们可以花的最少aacms每月维护道路,将连接所有的村庄。村庄是通过我在上面的地图。右边的地图显示了道路,可以保持最便宜,每月216 aacms。

你的任务是编写一个程序,将解决这些问题。

输入格式

由一个$\red{100}$数据集,紧随其后的是最后一行只包含$\red{0}$。

每个数据集从一行只包含一个数字$\red{n}$,村庄的数量,$\red{1 < n < 27}$,村庄用第一个标记$\red{n}$的字母,大写。

每个数据集是与$\red{n - 1}$线完成,从村庄标签按字母顺序排列的。

每一行的一个村庄开始与村里的标签后跟一个数字,$\red{k}$,道路从这个村子到村庄的标签后面的字母。如果$\red{k}$大于$\red{0}$,继续行数据为每个$\red{k}$道路。

每个路是村里的数据标签的另一端路紧随其后aacms的月度维护成本。在下面的示例输入,第一个数据集和上面的地图。

输出格式

每行输出一个整数为每个数据集:最低成本aacms每月保持道路系统,连接所有的村庄。

样例

输入样例

9
A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 G 38
F 0
G 1 H 35
H 1 I 35
3
A 2 B 10 C 40
B 1 C 20
0

输出样例

216
30