题目描述
丛林道路网络的维护费用太高，理事会必须选择停止维护一些道路。如下图所示，在下面的地图中，村庄被标记为A～I。左边的地图显示了现在所有道路及每月的维护费用，每月可以用最少的费用维护一些道路，保证所有村庄都是连通的。右边的地图显示了最便宜的道路维护方案，每月的维护总费用为216元。
输入
输入由1～100个数据集组成，最后一行只包含0。每个数据集的第1行都为数字n （1<n <27），表示村庄的数量，对村庄使用字母表的前n 个大写字母标记。每个数据集都有n -1行描述，这些行的村庄标签按字母顺序排序。最后一个村庄没有道路。村庄的每条道路都以村庄标签开头，后面跟着一个从这个村庄到后面村庄的道路数k。如果k >0，则该行后面包含k 条道路的数据。每条道路的数据都是道路另一端的村庄标签，后面是道路的每月维护成本。维护费用是小于100的正整数，道路数量不会超过75条，每个村庄通往其他村庄的道路都不超过15条。
输出
对于每个数据集，都单行输出每月维护连接所有村庄的道路的最低费用。
样例输入 Copy
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
样例输出 Copy
216
30
提示
注意： 在数据的输入格式方面，A 2 B 12 I 25表示A关联两条边，包括A-B的边（边权为12）及A-I的边（边权为25）。