#include <iostream>
#define max 10000
using namespace std;

int main()
{
   int sum=0;//总路程
   int min, min_f , min_t, min_s;  //分别为最小值，最小值开始的值，最小值到达的值，顶点之间的边的最小权值 
   int v[7][7]={{-1,5,7,-1,-1,-1,2},{5,-1,-1,9,-1,-1,3},{7,-1,-1,-1,8,-1,-1},{-1,9,-1,-1,-1,4,-1},{-1,-1,8,-1,-1,5,4},{-1,-1,-1,4,5,-1,6},{2,3,-1,-1,4,6,-1}};
   char ch[7] = {'A','B','C','D','E','F','G'};        //-1表示两个点之间没有连线 
   bool V_[7];   //判断村庄是否路过，标记
   
   for(int i= 0;i<7;i++)   //边邻接关系的初始化
   {  
    	for(int j = 0; j< 7 ;j++)
		{
        	if(v[i][j]==-1)
			{
           		v[i][j]=max;
        	}
        	else if(i==j)
			{
        		v[i][j]=0;
			} 
    	}
   }
   V_[0] = true;//从A出发
   for(int n = 0;n < 6; n++)  //开始遍历7个点
   {               
        //  数据初始化
        min_f = 0;
        min_t = 0;
        min = max;
		int i,j;
		
        for(int i= 0;i<7;i++) //找出发点
		{               
        	if(!V_[i])  //如果i不是已访问过的结点，则寻找下一个节点
			{
        		continue;
			} 
        	for(int i=1;i<=7;i++)    //寻找未被收录顶点中的最小值 
			{
        		if((v[i][j]<min)&&(v[i][j]!=0))
				{
        			min_s=v[i][j];
        			j=i;
				}
			}
			int j; 
			v[i][j]=0;               
        	for(int j = 0; j< 7 ;j++)   //找到最小边， j表示未访问过的结点
			{          
            	if(v[i][j] == max)
				{
            		continue;
				}  
            	
           		if(v[i][j]<min)   //如果当前min大于当前两个结点(这两个结点一个为已访问，一个为未访问)的最小路径，则替换当前的最小路径为当前两个结点的路径
				{
                	if(V_[j]!=0)
					{
                		continue;  //如果被标记了，跳过。
					}
					   
                	min = v[i][j];
                	min_t = i;
                	min_f = j;//记录下标
           		}
        	}
       }
       cout<<ch[min_t]<<" -> "<<ch[min_f]<<" "<<v[min_t][min_f]<<endl;
       V_[min_f] = true;
       sum += v[min_t][min_f];
   }
    cout<<"总路程："<<sum<<endl;
    return 0;
}