#include <cmath>
#include <iostream>
#include <algorithm>
#include <climits>
#include <vector>
using namespace std;

int n, m;
int b[200][200];

int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    cin >> n >> m;

    vector <pair<int, pair<int, int>>> a(m + 1);

    for (int i = 0; i < m; i++)
    {
        int t1, t2, t3;
        cin >> t1 >> t2 >> t3;
        a[i].first = t3;
        a[i].second.first = t1 - 1;
        a[i].second.second = t2 - 1;
    }

    sort(a.begin(), a.end());

    vector <int> tr(n + 1);
    vector < pair<int, int> > res;

    for (int i = 0; i < n; i++)
        tr[i] = i;

    int c = 0;

    for (int i = 0; i < m; i++)
    {
        int s = a[i].second.first;
        int e = a[i].second.second;
        int w = a[i].first;

        if (tr[s] != tr[e])
        {
            b[s][e] = w;
            b[e][s] = w;
            res.push_back(make_pair(s, e));
            int to = tr[e];
            int tn = tr[s];
            c += w;

            for (int j = 0; j < n; j++)
            {
                if (tr[j] == to)
                    tr[j] = tn;
            }
        }
    }

    cout << c << endl;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
            cout << b[i][j] << " ";
        cout << endl;
    }
    return 0;
}