Description

丛林道路网络的维护费用太高，理事会 必须选择停止维护一些道路。如下图所示，在下面的地图中，村庄被标 记为$A～I$。左边的地图显示了现在所有道路及每月的维护费用，每月可 以用最少的费用维护一些道路，保证所有村庄都是连通的。右边的地图 显示了最便宜的道路维护方案，每月的维护总费用为$216$元。

Format

Input

输入由$1～100$个数据集组成，最后一行只包含$0$。每个数据 集的第$1$行都为数字$n$ （$10$，则该行后面包含$k$ 条道路的数据。每条道路的数据都是道路另一端 的村庄标签，后面是道路的每月维护成本。维护费用是小于$100$的正整 数，道路数量不会超过$75$条，每个村庄通往其他村庄的道路都不超过$15$ 条。

Output

对于每个数据集，都单行输出每月维护连接所有村庄的道 路的最低费用。

Samples

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