#include<iostream>
using namespace std;

int ans=10000,mp[100][100],n,m,vis[100][100];
int dx[]={-1,1,0,0},dy[]={0,0,1,-1};
void dfs(int x,int y,int money,int magic)//x,y是位置，magic是 是否能施法 
{
	if(x==n&&y==n&&ans>money)
	{
		ans=money;
	}
	else{
		for(int i=0;i<4;i++)
		{
			int xx=x+dx[i];
			int yy=y+dy[i];
			if(xx>0&&xx<=n&&yy>0&&yy<=n&&!vis[xx][yy])//可以前进,没来过 
			{
				vis[xx][yy]=1;
				if(mp[xx][yy]==mp[x][y])//同颜色 
				{
					dfs(xx,yy,money,1);
				} 
				if(mp[xx][yy]==0&&magic)
				{
					magic=0;
					mp[xx][yy]=mp[x][y];//改颜色 
					dfs(xx,yy,money+2,0);
					mp[xx][yy]=0; 
				}
				if(mp[xx][yy]!=0&&mp[xx][yy]!=mp[x][y]){
					dfs(xx,yy,money+1,1);//不同颜色 
				}
				vis[xx][yy]=0;
			} 
		}
	}
}
int main ()
{
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		int x,y,c;
		cin>>x>>y>>c;
		mp[x][y]=c;
	}
	vis[1][1]=1;
	dfs(1,1,0,1);
	if(ans==10000)
	{
		cout<<-1;
		return 0;
	} 
	cout<<ans; 
}