#define _CRT_SECURE_NO_WARNINGS
#define INF 10e9
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <queue>
#include <stack>
#include <climits>

using namespace std;

long n, m, root = 0, dest, len = 0;

vector <vector<long>> gr;
vector <vector<long>> rebro;
vector <long> derevo;
vector <bool> used;
vector <int> parent;
queue <long> minpath;

int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    scanf("%ld%ld", &n, &m);
    gr.resize(n);
    rebro.resize(m);
    derevo.resize(m + 1);

    for (long i = 0; i < n; i++)
    {
        gr[i].resize(n);
        derevo[i] = i;
    }

    for (long i = 0; i < m; i++)
    {
        rebro[i].resize(3);
        scanf("%ld%ld%ld", &rebro[i][1], &rebro[i][2], &rebro[i][0]);
    }
    sort(rebro.begin(), rebro.end());

    for (long i = 0; i < m; i++)
    {
        long a = rebro[i][1];
        long b = rebro[i][2];
        long c = rebro[i][0];
        if (derevo[a] != derevo[b])
        {
            len += c;
            gr[a - 1][b - 1] = c;
            gr[b - 1][a - 1] = c;
            long aa = derevo[a];
            long bb = derevo[b];
            for (long j = 0; j < m + 1; j++)
            {
                if (derevo[j] == bb)
                {
                    derevo[j] = aa;
                }
            }
        }
    }

    printf("%ld\n", len);

    for (long i = 0; i < n; i++)
    {
        for (long j = 0; j < n; j++)
        {
            printf("%ld ", gr[i][j]);
        }
        printf("\n");
    }
    system("PAUSE");
    return 0;
}