#include <stdio.h>
#include <stdlib.h>
 
#define MAX 100
#define MAXCOST 0x7fffffff
 
int graph[MAX][MAX];
 
int Prim(int graph[][MAX], int n)
{
 /* lowcost[i]記錄以i為終點(diǎn)的邊的最小權(quán)值，當(dāng)lowcost[i]=0時(shí)表示終點(diǎn)i加入生成樹 */
 int lowcost[MAX];
 
 /* mst[i]記錄對(duì)應(yīng)lowcost[i]的起點(diǎn)，當(dāng)mst[i]=0時(shí)表示起點(diǎn)i加入生成樹 */
 int mst[MAX];
 
 int i, j, min, minid, sum = 0;
 
 /* 默認(rèn)選擇1號(hào)節(jié)點(diǎn)加入生成樹，從2號(hào)節(jié)點(diǎn)開始初始化 */
 for (i = 2; i <= n; i++)
 {
 /* 最短距離初始化為其他節(jié)點(diǎn)到1號(hào)節(jié)點(diǎn)的距離 */
 lowcost[i] = graph[1][i];
 
 /* 標(biāo)記所有節(jié)點(diǎn)的起點(diǎn)皆為默認(rèn)的1號(hào)節(jié)點(diǎn) */
 mst[i] = 1;
 }
 
 /* 標(biāo)記1號(hào)節(jié)點(diǎn)加入生成樹 */
 mst[1] = 0;
 
 /* n個(gè)節(jié)點(diǎn)至少需要n-1條邊構(gòu)成最小生成樹 */
 for (i = 2; i <= n; i++)
 {
 min = MAXCOST;
 minid = 0;
 
 /* 找滿足條件的最小權(quán)值邊的節(jié)點(diǎn)minid */
 for (j = 2; j <= n; j++)
 {
  /* 邊權(quán)值較小且不在生成樹中 */
  if (lowcost[j] < min && lowcost[j] != 0)
  {
  min = lowcost[j];
  minid = j;
  }
 }
 /* 輸出生成樹邊的信息:起點(diǎn)，終點(diǎn)，權(quán)值 */
 printf("%c - %c : %d\n", mst[minid] + 'A' - 1, minid + 'A' - 1, min);
 
 /* 累加權(quán)值 */
 sum += min;
 
 /* 標(biāo)記節(jié)點(diǎn)minid加入生成樹 */
 lowcost[minid] = 0;
 
 /* 更新當(dāng)前節(jié)點(diǎn)minid到其他節(jié)點(diǎn)的權(quán)值 */
 for (j = 2; j <= n; j++)
 {
  /* 發(fā)現(xiàn)更小的權(quán)值 */
  if (graph[minid][j] < lowcost[j])
  {
  /* 更新權(quán)值信息 */
  lowcost[j] = graph[minid][j];
 
  /* 更新最小權(quán)值邊的起點(diǎn) */
  mst[j] = minid;
  }
 }
 }
 /* 返回最小權(quán)值和 */
 return sum;
}
 
int main()
{
 int i, j, k, m, n;
 int x, y, cost;
 char chx, chy;
 
 /* 讀取節(jié)點(diǎn)和邊的數(shù)目 */
 scanf("%d%d", &m, &n);
 getchar();
 
 /* 初始化圖，所有節(jié)點(diǎn)間距離為無窮大 */
 for (i = 1; i <= m; i++)
 {
 for (j = 1; j <= m; j++)
 {
  graph[i][j] = MAXCOST;
 }
 }
 
 /* 讀取邊信息 */
 for (k = 0; k < n; k++)
 {
 scanf("%c %c %d", &chx, &chy, &cost);
 getchar();
 i = chx - 'A' + 1;
 j = chy - 'A' + 1;
 graph[i][j] = cost;
 graph[j][i] = cost;
 }
 
 /* 求解最小生成樹 */
 cost = Prim(graph, m);
 
 /* 輸出最小權(quán)值和 */
 printf("Total:%d\n", cost);
 
 //system("pause");
 return 0; 
}

void Kruskal(Edge E[],int n,int e)
{
 int i,j,m1,m2,sn1,sn2,k;
 int vset[MAXE];
 for (i=0;i<n;i++) vset[i]=i; //初始化輔助數(shù)組
 k=1;          //k表示當(dāng)前構(gòu)造最小生成樹的第幾條邊,初值為1
 j=0;          //E中邊的下標(biāo),初值為0
 while (k<n)      //生成的邊數(shù)小于n時(shí)循環(huán)
 { 
  m1=E[j].u;m2=E[j].v;    //取一條邊的頭尾頂點(diǎn)
 sn1=vset[m1];sn2=vset[m2]; //分別得到兩個(gè)頂點(diǎn)所屬的集合編號(hào)
 if (sn1!=sn2)    //兩頂點(diǎn)屬于不同的集合,該邊是最小生成樹的一條邊
 { 
  printf(" (%d,%d):%d/n",m1,m2,E[j].w);
  k++;          //生成邊數(shù)增1
  for (i=0;i<n;i++)    //兩個(gè)集合統(tǒng)一編號(hào)
   if (vset[i]==sn2)  //集合編號(hào)為sn2的改為sn1
       vset[i]=sn1;
 }
 j++;     //掃描下一條邊
 }
}