#include <iostream>
#include <cstdio>
using namespace std;

const int MAXN = 1000;

int N, M, a[MAXN][MAXN], c[MAXN][MAXN];

void input()
{
    scanf("%d %d", &N, &M);
    int from, to, price;
    for( int i = 0; i < M; i++ )
    {
        scanf("%d %d %d", &from, &to, &price);
        a[from-1][to-1] = a[to-1][from-1] = 1;
        c[from-1][to-1] = c[to-1][from-1] = price;
    }
}

bool used[MAXN];
void dfs( int i )
{
    used[i] = 1;
    for( int j = 0; j < N; j++ )
    {
        if( a[i][j] == 1 && !used[j] )
        {
            a[i][j] = a[j][i] = 2;
            dfs(j);
        }
    }
}

void print()
{
    for( int i = 0; i < N; i++ )
    {
        for( int j = 0; j < N; j++ )
            cout << a[i][j] << " ";
        cout << endl;
    }
}

int getPrice()
{
    int sum = 0;
    for( int i = 0; i < N-1; i++ )
    {
        for( int j = i+1; j < N; j++ )
            if( a[i][j] == 2 )
                sum += c[i][j];
    }
    return sum;
}

int main()
{
    input();
    dfs(0);

    print();

    cout << getPrice() << endl;

    return 0;
}
/**

5 7
1 2 3
2 5 3
1 4 5
2 4 10
2 3 1
4 3 1
3 5 2

Sorted:
2 3 1
4 3 1
3 5 2
1 2 3
2 5 3
1 4 5
2 4 10

**/