#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

const char iname[] = "maxflow.in";
const char oname[] = "maxflow.out";
const int  nmax    = 1000;

ifstream fin(iname);
ofstream fout(oname);

vector<int> Gr[nmax];
queue<int> Q;
bool viz[nmax];
int T[nmax], C[nmax][nmax], F[nmax][nmax];
int m, n, x, y, c, fmini, flow;
int j, i;

int BFS()
{	
	int i, j, x;
	for(int i = 1; i <= n; i ++)
		viz[i] = 0;
	viz[1] = 1;
	Q.push(1);
	
	while(!Q.empty())
	{
		x = Q.front();
		Q.pop();
		for(vector<int>::iterator it = Gr[x].begin(); it != Gr[x].end(); ++ it)
		{
			if(viz[*it] == 0 && F[x][*it] < C[x][*it])
			{
				T[*it] = x;
				viz[*it] = 1;
				Q.push(*it);
				if(*it == n)
					return 1;
			}
		}
	}
	return 0;
}


int main()
{
	fin >> n >> m;
	for(i = 1; i <= m; i ++)
	{
		fin >> x >> y >> c;
		C[x][y] = c;
		Gr[y].push_back(x);
		Gr[x].push_back(y);
	}
	
	while(BFS())
	{	
		fmini = 2819889;
		for(i = n; i != 1; i = T[i])
			fmini = min(fmini, C[T[i]][i] - F[T[i]][i]);
		for(i = n; i != 1; i = T[i])
		{
			F[T[i]][i] += fmini;
			F[i][T[i]] -= fmini;
		}
		flow += fmini;
		for(i = 1; i <= n; i ++)
			T[i] = 0;
		while(!Q.empty())
			Q.pop();
	}

	fout << flow << "\n";
	for(i = 1; i <= n; i ++)
	{
		for(j = 1; j <= n; j ++)
			cout << F[i][j] << " ";
		cout << "\n";
	}
	return 0;
}