#include<bits/stdc++.h>
using namespace std;
#define f(a,c,b) for(int a = c;a<=b;a++)
int mp[1010][1010];
int vis[1010][1010];
int jiyi[1010][1010];
int tx[4] = {0,1,0,-1};
int ty[4] = {1,0,-1,0};
int m,n;
int ans = INT_MAX;
int dfs(int x,int y,int coin,bool magic)
{
	bool F = 0;
	if(jiyi[x][y] != -1 && jiyi[x][y] < coin)
	{
		return 0;
	}
	if(jiyi[x][y] != -1)
	{
		jiyi[x][y] = coin;
	}
	if(x == m and y == m)
	{
		ans = min(ans,coin);
		return 0;
	}
	for(int i = 0;i<4;i++)
	{
		int nx = x+tx[i];  int ny = y+ty[i];
		if(nx >= 1 && ny >= 1 && nx <= m && ny <= m && vis[nx][ny] != 1 && mp[nx][ny] != 0)
		{
			vis[nx][ny] = 1;
			dfs(nx,ny,coin + abs(mp[x][y] - mp[nx][ny]),0);
			F = 1;
			vis[nx][ny] = 0;
		}
		else if(mp[nx][ny] == 0 and magic == 0)
		{
			if(nx >= 1 && ny >= 1 && nx <= m && ny <= m && vis[nx][ny] != 1)
			{		
				vis[nx][ny] = 1;
				mp[nx][ny] = mp[x][y];
				dfs(nx,ny,coin+2,1);
				mp[nx][ny] = 0;
				vis[nx][ny] = 0;
			}
		}
	}
	return 0;
}
int main()
{
	cin >> m >> n;
	int x,y,z;
	memset(jiyi,-1,sizeof jiyi);
	f(i,1,n)
	{
		cin >> x >> y >> z;
		mp[x][y] = z+1;
	}
	dfs(1,1,0,0);
	if(ans != INT_MAX)
	{
		cout << ans << '\n';
	}
	else
	{
		cout << "-1\n";
	}
}

大犇快来看看啊！！！！