题目描述

热带岛屿拉格里山的首席长老有问题。几年前，大量外援资金被用于修建村庄之间的额外道路。但丛林无情地超越道路，因此大型道路网络的维护成本太高。长老议会必须选择停止维护一些道路。左上方的地图显示了所有正在使用的道路以及每月维护这些道路的成本（以 aacms 为单位）。当然，即使路线不像以前那么短，也需要通过某种方式在维护的道路上到达所有村庄。首席长老想告诉长老委员会，他们每个月可以在 aacms 上花费的最少金额来维护连接所有村庄的道路。在上面的地图中，村庄被标记为 A 到 I。右边的地图显示了可以最便宜地维护的道路，每月 216 aacms。你的任务是编写一个程序来解决这些问题。

输入格式

输入由1到100个数据集组成，最后一行只包含0。 每个数据集以一行开始，只包含一个数字n，它是村庄的数量，1 < n < 27，村庄被标记字母表的前 n 个字母大写。每个数据集都由 n-1 行完成，这些行以字母顺序以村庄标签开头。最后一个村庄没有线路。一个村庄的每条线都以村庄标签开始，然后是从这个村庄到字母表中带有标签的村庄的道路数量 k。如果 k 大于 0，则该行继续包含 k 条道路中每条道路的数据。每条道路的数据是道路另一端的村庄标签，然后是道路的每月维护成本（以 aacms 为单位）。维护成本将是小于 100 的正整数。行中的所有数据字段都由单个空格分隔。公路网将始终允许在所有村庄之间通行。该网络的道路永远不会超过 75 条。没有一个村庄有超过 15 条通往其他村庄的道路（字母表中的之前或之后）。在下面的示例输入中，第一个数据集与上面的地图一致。

输出格式

每个数据集的每行输出一个整数：维护连接所有村庄的道路系统的每月最低成本（以 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

源poj1251