题目描述：

Lagrishan热带岛屿的长老遇到了一个问题。几年前，一笔外国援助资金被用于修建村庄之间的额外道路。但由于丛林不断侵蚀道路，庞大的道路网络维护成本过高。长老会必须决定停止维护部分道路。左上图显示了当前所有使用中的道路及其每月的维护成本（单位：aacms）。他们需要确保在维护的道路上仍能连通所有村庄，即使路线不如从前便捷。首席长老希望告诉长老会每月维持村庄连通所需的最低维护成本。村庄用字母A到I标记。右上图显示了最优维护方案，每月成本为216 aacms。你的任务是编写程序解决此类问题。

输入格式：

• 输入包含1到100个数据集，最后以单独一行0结束。
• 每个数据集首行为村庄数量n（1 < n < 27），村庄用字母表前n个大写字母标记。
• 随后n-1行按字母顺序描述每个村庄（最后一个村庄无数据）：
  • 每行以村庄标签开头，后接该村庄到后续字母村庄的道路数k。
  • 若k>0，接着给出k条道路数据：目标村庄标签和每月维护成本（正整数<100）。
• 所有字段用单个空格分隔。
• 道路网络保证所有村庄互通。
• 道路总数不超过75条。
• 每个村庄连接其他村庄的道路不超过15条。

输出格式：

• 每个数据集输出一行整数：连通所有村庄的最低月维护成本。

示例输入输出：

输入示例 1：

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

输出示例 1：

216
30