#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define DEBUG 0
#define false 0
#define true 1

int** AdjacencyMatrix;                                                         // 用來記錄點與點之間的關係，若是[a][b] = 1 代表可以由a走到b 且edge 的重量為1  若[a][b] = 0 則代表兩點不相交
int* predecessor;                                                               // 紀錄最後在MST中 每個點之間parent-child 關係，跟第C題Version 1 的Parent矩陣功能一樣
unsigned int* key;                                                                       // 紀錄到達該點最低的成本 若是確定該成本為最低，則該兩點放入predecessor ex: 若是到達b 最短的距離是從a出發重量為2 則 key[b] = 2 且 predecessor[b] = a
int* visited;                                                                   // 如果一個點已經被放入predecessor(MST) 則標示為1 其他為0

int V;
int E;

void    PrimMST             (int start);
int     Select_Min_Key      (void);
void    Check_Connected_Edge(int K);
void    Print_MST           (int start);
void    Print_Total_Weight  (void);
void    Print_AdjacencyMatrix(void);
void    Print_Support_Matrix(void);

int main (){
    int i;
    scanf("%d %d",&V, &E);
    if(DEBUG)printf("V = %d  :  E = %d\n",V,E);

//C語言要動態開二為矩陣比較麻煩點 總之以下這段等價於 new int[V][V]
//**********************************************************//
    AdjacencyMatrix     = (int **)malloc(sizeof(int*)*V);
    for(i = 0; i< V; i++){
        AdjacencyMatrix[i] = (int *)malloc(sizeof(int)*V);
        if(AdjacencyMatrix[i] == NULL){
            if(DEBUG)printf("Out Of Memory !!Meow!! \n");
            return 1;
        }
        memset(AdjacencyMatrix[i],0,sizeof(int)*V);    
    }
//*********************************************************//

    predecessor         = malloc(sizeof(int)*V);
    key                 = malloc(sizeof(int)*V);
    visited             = malloc(sizeof(int)*V);

    if( AdjacencyMatrix == NULL || predecessor == NULL || key == NULL || visited == NULL){
        if(DEBUG)printf("Out Of Memory !!Meow!! \n");
        return 1;
    }
    // 檢查是否記憶體不足 沒辦法全部初始化空間 (理論上不會 如果會的話也太扯了)

    memset(predecessor,     -1,         sizeof(int)*V);
    memset(key,             INT_MAX,    sizeof(int)*V);
    memset(visited,         false,      sizeof(int)*V);
    // 初始化每個陣列


    int s;                                                                      // Source
    int t;                                                                      // Target
    int w;                                                                      // Weight
    // 宣告建立AdjacencyMatrix 會用到的變數

    while(E>0){
        scanf("%d %d %d",&s, &t, &w);
        AdjacencyMatrix[s][t] = w;
        AdjacencyMatrix[t][s] = w;                                              // 因為這個graph沒有方向性 代表不論 s->t or t->s 重量都會一樣
        E--;
    }
    // 使用迴圈接收input 並且把他們填入AdjacencyMatrix

    if(DEBUG)Print_AdjacencyMatrix();

    PrimMST(2);
    // 開始進行MST主要作業 起點可以任意設置，在此統一用0

    if(DEBUG)Print_Support_Matrix();
    if(DEBUG)Print_MST(2);

    Print_Total_Weight();

    return 0;
}

void PrimMST(int start){
    // 此演算法核心 ==>      1. 挑出key 最小的放入MST
    //                      2. 更新visited 代表這個點已經被放入MST
    //                      3. 比較周遭相連的edge 跟 點 ，如果從剛挑出來的key出發會重量比較輕 就設定上去 (更新key[] 與 predecessor[])

    int K;                                                                      // 大寫 K 代表目前被挑選出來的 key 最小的點
    int v = 0;                                                                  // 小寫 v 被初始化成 V (總共幾個點) 用來給迴圈扣 扣到 0 等於所有點都放進MST了
    int X;                                                                      // 大寫 X 代表比較edge的時候，由 K 出發可到達的終點
    key[start] = 0;
    // 到達起點的權重當然是0

    while(v < V){
        if(DEBUG)printf("\n----------------------------\nThe %3dth loop\n",v+1);

        K = Select_Min_Key();
        if(DEBUG)printf("K = %3d\n",K);
        // 步驟一
        
        visited[K] = 1;
        // 步驟二

        Check_Connected_Edge(K);
        // 步驟三
        if(DEBUG)Print_Support_Matrix();
        v++;
    }
    // 主迴圈
    
}

int Select_Min_Key(void){
    int min = INT_MAX;
    int min_index;
    int i;
    for(i = 0; i< V; i++){
        if(key[i] < min && visited[i] == false){
            min = key[i];
            min_index = i;
        }
    }
    return min_index;
}

void Check_Connected_Edge(int K){
    int i;

    for (i = 0; i< V; i++){

        if(visited[i] == false){ //挑選出還沒放入MST的點

            if( AdjacencyMatrix[K][i] != 0){ //挑選出與K相連的點

                if(AdjacencyMatrix[K][i] < key[i]){ //如果經由 K 走到 i 的重量 小於 上次紀載的 從任意一個點走向 i 的重量還小  就把這個重量更新上去。 因為最終目標是找出 走到i 最輕的路徑

                    predecessor[i] = K;                         //因為從K 走到 i 最短 所以紀錄下來 (幾乎等同放進MST 只是還沒更新visited 因為還沒確定)
                    key[i] = AdjacencyMatrix[K][i];             //同理 重量也記錄下來

                }

            }

        }
    }

}


void Print_MST(int start){
    int i;

    printf("MST find by Prim :\n");
    printf(" v1 -  v2 : weight\n");

    i = (start+1)%V;
    while(i != start){
        printf("%3d - %3d :%5d\n", predecessor[i],i,AdjacencyMatrix[predecessor[i]][i]);
        i = (++i)%V;
    }

}


void    Print_Total_Weight  (void){
    int i;
    int weight = 0;
    
    for(i = 0; i<V ; i++){
        weight += key[i];
    }

    printf("%d\n",weight);

}

void    Print_AdjacencyMatrix(void){
    int i;
    int j;
    for(i = 0; i< V; i++){
        for(j = 0; j<V; j++){
            printf("%3d ",AdjacencyMatrix[i][j]);
        }
        printf("\n");
    }
}

void    Print_Support_Matrix(void){
    int i;
    printf("predecessor[] : ");
    for(i = 0; i< V; i++){
        printf("%3d",predecessor[i]);
    }
    printf("\n");
    printf("        key[] : ");
    for(i = 0; i< V; i++){
        printf("%3d",key[i]);
    }
    printf("\n");
    printf("    visited[] : ");
    for(i = 0; i< V; i++){
        printf("%3d",visited[i]);
    }
    printf("\n");
}
