Background

设有一个 $m × m$ 的方格画布，该画布中的每一小格可能被染成红色、黄色或者保持空白。你的任务是从画布的最左上角走到最右下角。

你所站在的小格必须是被染色的（即不能是空白的），你可以向四个方向移动：上、下、左、右。若你从一个小格移动到另一个颜色相同的小格，你的金币数量不会改变；若颜色不同，则需要消耗 $1$ 枚金币。

此外，你可以投入 $2$ 枚金币使用魔法将即将进入的空白格子临时染成你所选的颜色。但是这个魔法不能连续使用，且只能持续很短的时间。这意味着，如果你想继续使用这个魔法，你必须先离开这个因魔法而临时被染过色的格子，移动到一个原有颜色的格子上。而当你离开一个有魔法颜色的格子后，小格将恢复原有的无色状态。

请计算从画布最左上角移动到最右下角至少需要消耗多少金币？

Input

第一行有两个正整数 $m,n$ ，以一个空格分隔，分别表示画布的大小和已经被染过色的小格的数量。

接下来的 $n$ 行，每行三个正整数 $x,y,z$ ，分别表示在 $(x, y)$ 坐标的小格已被染过颜色 $c$ 。其中， $c=1$ 代表黄色， $c=0$ 代表红色。各个数之间以一个空格隔开。

画布左上角的坐标为 $(1,1)$ ，右下角的坐标为 $(m,m)$ 。

一个整数，表示至少需要消耗的金币数量。如果无法到达最右下角，输出 $-1$ 。

-1

对于 $30\%$ 的数据, $1<m<5,1<n<10$

对于 $60\%$ 的数据, $1<m<20,1<n<200$

对于 $100\%$ 的数据, $1<m<100,1<n<1,000$