题目描述

热带岛屿拉格里山的首席长老有一个问题。几年前，大量的外国援助资金花在了村与村之间的额外道路上。但是丛林无情地超过了道路，所以大型的道路网维护起来太贵了。长老会必须选择停止修路。上面左边的地图显示了所有正在使用的道路，以及维护这些道路每月的成本。当然，需要有一些方法来在维护道路上的所有村庄之间穿行，即使路线没有以前那么短。

现在老王的同学承包了这个维护道路项目，他刚刚学习了prim算法，但是刚刚入门的他，只会套用模板，所以他想通过这个工程来深入学习一下prim，你的任务是写一个程序，告诉他这个算法的每一步是如何连接的村庄。

输入格式

输入由一到100个数据集组成，最后一行只包含0。每个数据集以一条仅包含数字n的行开始，即村庄数，1

输出格式

输出包括算法每一步连接的村庄（从A村庄开始），每一步占一行输出，最后输出维护所需要的费用。

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

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

提示

物联1802 周伟剑