#include<bits/stdc++.h>
#define isdi(a) ((a)>='0'&&(a)<='9')
#define gc getchar()
#define pc(a) putchar(a)
#define writeln(a) write(a,'\n')
//#define int long long
#define ll long long
#define fio(a) freopen((string(a)+".in").c_str(),"r",stdin);freopen((string(a)+".out").c_str(),"w",stdout);
using namespace std;

template<typename T>
void read(T&r)
{
	r=0;char ch=gc,last='z';
	while(!isdi(ch)) last=ch,ch=gc;
	while(isdi(ch)) r=(r<<1)+(r<<3)+(ch^48),ch=gc;
	if(last=='-') r=-r;
}

template<typename... T>
void reads(T& ...rr)
{
	for(auto r:{&rr...})
	{
		(*r)=0;char ch=gc,last='z';
		while(!isdi(ch)) last=ch,ch=gc;
		while(isdi(ch)) (*r)=((*r)<<1)+((*r)<<3)+(ch^48),ch=gc;
		if(last=='-') (*r)=-(*r);
	}
}

int buf[100],len_;
template<typename T>
void write(T r,char endc=' ')
{
	if(r<0) pc('-'),r=-r;
	len_=0;
	do buf[len_++]=r%10; while(r/=10);
	for(int i=len_-1;i>=0;i--) pc(buf[i]+'0');
	if(endc!=0) pc(endc);
}

template<typename... T>
void writes(T ...ww)
{
	char endc=' ';
	for(auto w:{ww...})
	{
		if(w<0) pc('-'),w=-w;
		len_=0;
		do buf[len_++]=w%10; while(w/=10);
		for(int i=len_-1;i>=0;i--) pc(buf[i]+'0');
		pc(endc);
	}
	pc('\n');
}

struct Edge{
	int from,to,cap;
};
vector<Edge> edges;
vector<int> G[100010];
int m,n;

void ins(int from,int to,int cap)
{
	// writeln(cap);
	edges.push_back({from,to,cap});
	G[from].push_back(edges.size()-1);
}

int mp[101][101];
int tx[4]={1,0,-1,0},
	ty[4]={0,1,0,-1};

int gn(int x,int y)
{
	// writes(x,y,0);
	return (x-1)*m+(y-1)%m;
}

int gn2(int x,int y)  //mp[x][y] has no color, and change it into 1
{
	// writes(x,y,1);
	return m*m+(x-1)*m+(y-1)%m;
}

struct Node{
	int x,dist;
	bool operator < (Node b) const
	{
		Node a=*this;
		return a.dist>b.dist;
	}
};

priority_queue<Node> q;
int dist[100100];
bool vis[100100];
bool dij(int s)
{
	memset(vis,0,sizeof(vis));
	memset(dist,63,sizeof(dist));
	dist[s]=0;
	q.push({s,0});
	while(!q.empty())
	{
		Node t=q.top();q.pop();
		if(vis[t.x]) continue;
		vis[t.x]=true;
		for(int i=0;i<G[t.x].size();i++)
		{
			Edge e=edges[G[t.x][i]];
			if(dist[e.to]>dist[e.from]+e.cap)
			{
				dist[e.to]=dist[e.from]+e.cap;
				q.push({e.to,dist[e.to]});
			}
		}
	}
	return vis[gn(m,m)]||vis[gn2(m,m)];
}

int main()
{
	memset(mp,-63,sizeof(mp));
	int x,y,c;
	reads(m,n);
	for(int i=1;i<=n;i++)
	{
		reads(x,y,c);
		mp[x][y]=c;
	}
	// puts("");
	for(int i=1;i<=m;i++)
		for(int j=1;j<=m;j++)
			if(mp[i][j]==0)
			{
				for(int k=0;k<4;k++)
				{
					int nx=i+tx[k],ny=j+ty[k];
					if(nx<=0||nx>m||ny<=0||ny>m) continue;
					if(mp[nx][ny]==0) ins(gn(i,j),gn(nx,ny),0);
					if(mp[nx][ny]==1) ins(gn(i,j),gn(nx,ny),1);
					if(mp[nx][ny]<0) ins(gn(i,j),gn(nx,ny),2),ins(gn(i,j),gn2(nx,ny),3);
				}
			}
			else if(mp[i][j]==1)
			{
				for(int k=0;k<4;k++)
				{
					int nx=i+tx[k],ny=j+ty[k];
					if(mp[nx][ny]==1) ins(gn(i,j),gn(nx,ny),0);
					if(mp[nx][ny]==0) ins(gn(i,j),gn(nx,ny),1);
					if(mp[nx][ny]<0) ins(gn(i,j),gn(nx,ny),3),ins(gn(i,j),gn2(nx,ny),2);
				}
			}
			else
			{
				for(int k=0;k<4;k++)
				{
					int nx=i+tx[k],ny=j+ty[k];
					if(mp[nx][ny]==1) ins(gn(i,j),gn(nx,ny),1),ins(gn2(i,j),gn(nx,ny),0);
					if(mp[nx][ny]==0) ins(gn(i,j),gn(nx,ny),0),ins(gn2(i,j),gn(nx,ny),1);
				}
			}
	// puts("");
	if(!dij(gn(1,1))) puts("-1");
	else
	{
		// writeln(gn2(m,m));
		writeln(min(dist[gn(m,m)],dist[gn2(m,m)]));
	}
	return 0;
}