#include <bits/stdc++.h>
using namespace std;

int m,n,ans;
int a[105][105];
bool v[105][105];

struct node{
	int x,y,coin;
	bool magic;
	int colour;
	bool operator <(const node &a)const{
		return a.coin<coin;
	}
};

priority_queue<node> q;

void bfs(){
	node di;
	while (q.size()){
		di = q.top();
		q.pop();
		cout << di.x << ' ' << di.y << ' ' << di.coin << ' ' << di.magic << ' ' << di.colour<<endl;
		if (di.x==m && di.y==m){
			ans = di.coin;
			return;
		}
		int xx = di.x + 1;
		if (xx<=m && v[xx][di.y] == false){
			if (a[xx][di.y] == di.colour && a[xx][di.y] != 0 && di.colour != 0){
				q.push({xx,di.y,di.coin,true,a[xx][di.y]});
				v[xx][di.y] = true;
			}
			else if (a[xx][di.y] != 0 && di.colour != 0){
				q.push({xx,di.y,di.coin+1,true,a[xx][di.y]});
				v[xx][di.y] = true;
			}
			else if(a[xx][di.y] == 0 && di.magic == true ){
				q.push({xx,di.y,di.coin+2,false,a[di.x][di.y]});
				q.push({xx,di.y,di.coin+3,false,3-a[di.x][di.y]});
				v[xx][di.y] = true;
			}
		}
		int yy = di.y + 1;
		if (yy<=m && v[di.x][yy] == false){
			if (a[di.x][yy] == di.colour && a[di.x][yy] != 0 && di.colour != 0){
				q.push({di.x,yy,di.coin,true,a[di.x][yy]});
				v[di.x][yy] = true;
			}
			else if (a[di.x][yy] != 0 && di.colour != 0){
				q.push({di.x,yy,di.coin+1,true,a[di.x][yy]});
				v[di.x][yy] = true;
			}
			else if(a[di.x][yy] == 0 && di.magic == true){
				q.push({di.x,yy,di.coin+2,false,a[di.x][di.y]});
				q.push({di.x,yy,di.coin+3,false,3-a[di.x][di.y]});
				v[di.x][yy] = true;
			}
		}
	}
	if (di.x!=m || di.y!=m){
		ans = -1;
	}
}

int main(){
	cin >> m >> n;
	for (int i=1;i<=n;i++){
		int x,y,c;cin >> x >> y >> c;
		a[x][y] = c+1;
	}
	// 0->无色，1->红色，2->黄色
	
	q.push({1,1,0,true,a[1][1]});
	v[1][1] = true;
	bfs();
	cout << ans << endl;
	
	for (int i=1;i<=m;i++){
		for (int j=1;j<=m;j++){
			cout << a[i][j] << ' ';
		}
		cout << endl;
	}
	
	
	
	return 0;
}