题目描述

以前小方是一个地主，周围的几个村庄都他的，他听说，“要想富先修路”，所以他找来了刚替热带岛屿拉格里山的首席长老解决了问题的老王。

现在老王承包了这个修道路项目，小方刚刚学习了Kruskal算法，但是刚刚入门的他，只会套用模板，所以他想通过这个工程来深入向老王学习一下Kruskal，现在你是老王，你需要写一个程序，告诉小方地主这个算法的每一步连接的是哪两个村庄。上面左边的地图显示了村庄间的道路，以及修这些道路的成本。

输入格式

输入由一到100个数据集组成，最后一行只包含0。每个数据集以一条仅包含数字n的行开始，即村庄数，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

B I
B C
A B
C D
G H
H I
E G
E F
216
A B
B C
30

提示

物联1802 周伟剑