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

int m,n,x,y,c;

int a[105][105],bx[12]={1,-1,0,0,2,0,-2,0,1,1,-1,-1},by[12]={0,0,-1,1,0,2,0,-2,-1,1,-1,1};

int vis[105][105],jb[105][105];

bool t=0,f=0;

int ans=0,tx,ty;

queue <int> p,q;

void bfs(){
	p.push(1);
	q.push(1);
	while(!p.empty()){
		tx=p.front();
		ty=q.front();
		if(tx==m&&ty==m){
			f=1;
			return;
		}
		for(int i=0;i<4;i++){
			if(a[tx][ty]==a[tx+bx[i]][ty+by[i]]&&vis[tx+bx[i]][ty+by[i]]==0){
				vis[tx+bx[i]][ty+by[i]]=1;
				jb[tx+bx[i]][ty+by[i]]=jb[tx][ty];
				p.push(tx+bx[i]);
				q.push(ty+by[i]);
			}
		}
		for(int i=0;i<4;i++){
			if(a[tx][ty]!=a[tx+bx[i]][ty+by[i]]&&a[tx+bx[i]][ty+by[i]]!=0&&vis[tx+bx[i]][ty+by[i]]==0){
				vis[tx+bx[i]][ty+by[i]]=1;
				jb[tx+bx[i]][ty+by[i]]=jb[tx][ty]+1;
				p.push(tx+bx[i]);
				q.push(ty+by[i]);
			}
		}
		for(int i=4;i<8;i++){
			if(a[tx][ty]==a[tx+bx[i]][ty+by[i]]&&vis[tx+bx[i]][ty+by[i]]==0){
				vis[tx+bx[i]][ty+by[i]]=1;
				if(jb[tx+bx[i]][ty+by[i]]!=0)jb[tx+bx[i]][ty+by[i]]=min(jb[tx+bx[i]][ty+by[i]],jb[tx][ty]+2);
				else jb[tx+bx[i]][ty+by[i]]=jb[tx][ty]+2;
				p.push(tx+bx[i]);
				q.push(ty+by[i]);
			}
		}
		for(int i=4;i<8;i++){
			if(a[tx][ty]!=a[tx+bx[i]][ty+by[i]]&&a[tx+bx[i]][ty+by[i]]!=0&&vis[tx+bx[i]][ty+by[i]]==0){
				vis[tx+bx[i]][ty+by[i]]=1;
				if(jb[tx+bx[i]][ty+by[i]]!=0)jb[tx+bx[i]][ty+by[i]]=min(jb[tx+bx[i]][ty+by[i]],jb[tx][ty]+3);
				else jb[tx+bx[i]][ty+by[i]]=jb[tx][ty]+3;
				p.push(tx+bx[i]);
				q.push(ty+by[i]);
			}
		}
		for(int i=8;i<12;i++){
			if(a[tx][ty]==a[tx+bx[i]][ty+by[i]]&&vis[tx+bx[i]][ty+by[i]]==0){
				vis[tx+bx[i]][ty+by[i]]=1;
				if(jb[tx+bx[i]][ty+by[i]]!=0)jb[tx+bx[i]][ty+by[i]]=min(jb[tx+bx[i]][ty+by[i]],jb[tx][ty]+2);
				else jb[tx+bx[i]][ty+by[i]]=jb[tx][ty]+2;
				p.push(tx+bx[i]);
				q.push(ty+by[i]);
			}
		}
		for(int i=8;i<12;i++){
			if(a[tx][ty]!=a[tx+bx[i]][ty+by[i]]&&a[tx+bx[i]][ty+by[i]]!=0&&vis[tx+bx[i]][ty+by[i]]==0){
				vis[tx+bx[i]][ty+by[i]]=1;
				if(jb[tx+bx[i]][ty+by[i]]!=0)jb[tx+bx[i]][ty+by[i]]=min(jb[tx+bx[i]][ty+by[i]],jb[tx][ty]+3);
				else jb[tx+bx[i]][ty+by[i]]=jb[tx][ty]+3;
				p.push(tx+bx[i]);
				q.push(ty+by[i]);
			}
		}
		p.pop();
		q.pop();
	}
	cout<<-1;
	return;
}

int main(){
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		cin>>x>>y>>c;
		a[x][y]=c+1;
	}
	bfs();
	cout<<jb[m][m]<<endl;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=m;j++){
			cout<<jb[i][j]<<" ";
		}
		cout<<endl;
	}
	

	return 0;
}