#include<bits/stdc++.h>
using namespace std;
const int maxn = 1005;
int n, m;
int d[maxn], vis[maxn], mat[maxn][maxn];
int main(){
    int End, ans = 0;
    memset(d, 0x3f, sizeof(d));
    memset(mat, 0x3f, sizeof(mat));
    d[1] = 0;
    scanf("%d%d", &n, &m);
    for(int i=0; i<m; i++){
        int t1, t2, t3;
        scanf("%d%d%d", &t1, &t2, &t3);
        mat[t1][t2] = t3;
        mat[t2][t1] = t3;
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            printf("%15d", mat[i][j]);
        }
        printf("\n");
    }
    for(int i=1; i<=n; i++){
        End = -1;
        for(int j=1; j<=n; j++){
            if(!vis[j] && (End==-1 || d[j]<d[End])){
                End = j;
            }
        }
        vis[End] = 1;
        ans += d[End];
        for(int j=1; j<=n; j++){
            if(!vis[j] && d[j]>mat[End][j]){
                d[j] = mat[End][j];
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}