#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
struct node{
	int xo,yo;
	bool tag;
};
int m,n,a[101][101],xni,yni,c,idx=0;
int xu[5]={0,0,1,-1},yu[5]={1,-1,0,0},golde[101][101];
int main()
{
	queue<node> q;
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		cin>>xni>>yni>>c;
		if(c==0)
		a[xni][yni]=-1;
		else a[xni][yni]=1;
	}
	for(int i=1;i<=m;i++){
	for(int j=1;j<=m;j++) 
	cout<<a[i][j]<<" ";	
	cout<<endl;
    }
	for(int i=1;i<=m;i++)
	for(int j=1;j<=m;j++)
	golde[i][j]=0x7fffffff;
	q.push((node){1,1,0});
	golde[1][1]=0;
	while(!q.empty()){
		node topi=q.front();
		q.pop();
		cout<<topi.xo<<" "<<topi.yo<<endl;
		for(int i=0;i<4;i++){
			int xn=topi.xo+xu[i],yn=topi.yo+yu[i];
			if(xn<=m&&xn>=1&&yn<=m&&yn>=1)
			{
				if(a[xn][yn]==0&&!topi.tag){
					q.push((node){xn,yn,1});
					golde[xn][yn]=min(golde[xn][yn],golde[topi.xo][topi.yo]+2);
				} 
				if(a[xn][yn]!=0&&a[xn][yn]==a[topi.xo][topi.yo]){
					q.push((node){xn,yn,0});
					golde[xn][yn]=min(golde[xn][yn],golde[topi.xo][topi.yo]);
				}
				if(a[xn][yn]!=0&&a[xn][yn]!=a[topi.xo][topi.yo]){
					q.push((node){xn,yn,0});
					golde[xn][yn]=min(golde[xn][yn],golde[topi.xo][topi.yo]+1);
				}
			}
		}
	}
	if(golde[m][m]==0x7fffffff) cout<<"-1";
	else cout<<golde[m][m];
	return 0;
}