#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define reg register int
#define msz(a) memset(a, 0, sizeof a);
#define rep1(i, j, n) for (reg i = j; i <= n; ++i)
#define rep2(i, j, n) for (reg i = j; i >= n; --i)
typedef long long LL;
typedef pair <int, int> PII;
const int INF1 = 0x3f3f3f3f, INF2 = 0x7fffffff;
const int M = 105;
int n, m, dx[] = { 0, 0, 1, -1 }, dy[] = { -1, 1, 0, 0 };
int a[M][M], ans = INF2, cost[M][M];
bool vis[M][M];
struct node {
    int x, y, charge, magic, lx, ly;
    node () {};
    node (int _x, int _y, int _charge, int _magic, int _lx, int _ly) { x = _x, y = _y, charge = _charge, magic = _magic, lx = _lx, ly = _ly; }
} ;
bool chk(int x, int y) { return 0 < x && x <= m && 0 < y && y <= m; }
void bfs() {
    queue <node> Q;
    Q.push(node (1, 1, 0, 0, 0, 0));
    vis[1][1] = 1;
    while (!Q.empty()) {
        node now = Q.front(); Q.pop();
        int x = now.x, y = now.y, charge = now.charge, magic = now.magic, lx = now.lx, ly = now.ly;
        if (magic == 1) a[x][y] = a[lx][ly];
        for (int i = 0; i < 4; ++i) {
            int tx = x + dx[i], ty = y + dy[i];
            if (!chk(tx, ty)) continue;
            if (magic == 1) {
                int p = a[x][y];
                if (a[tx][ty] == a[x][y] && a[x][y] != 0 && charge < cost[tx][ty]) 
                    cost[tx][ty] = charge, Q.push(node(tx, ty, charge, 0, x, y));
                // a[x][y] = p;
                if (((a[x][y] == 1 && a[tx][ty] == 2) || (a[x][y] == 2 && a[tx][ty] == 1)) && charge < cost[tx][ty] - 1) 
                    cost[tx][ty] = charge + 1, a[x][y] = 0, Q.push(node(tx, ty, charge + 1, 0, x, y));
            } else {
                if (a[tx][ty] == a[x][y] && a[x][y] != 0 && charge < cost[tx][ty]) 
                    cost[tx][ty] = charge, Q.push(node(tx, ty, charge, 0, x, y));
                else if (((a[x][y] == 1 && a[tx][ty] == 2) || (a[x][y] == 2 && a[tx][ty] == 1)) && charge < cost[tx][ty] - 1) 
                    cost[tx][ty] = charge + 1, Q.push(node(tx, ty, charge + 1, 0, x, y));
                if (a[x][y] != 0 && a[tx][ty] == 0 && charge + 2 < cost[tx][ty]) 
                    cost[tx][ty] = charge + 2, Q.push(node(tx, ty, charge + 2, 1, x, y));
            }
        }
        if (magic == 1) a[x][y] = 0;
    }
} 
int main() {
    scanf("%d%d", &m, &n);
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= m; ++j)
            cost[i][j] = INF2;
    for (int i = 1; i <= n; ++i) {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        a[x][y] = c + 1;
    }
    cost[1][1] = 0;
    bfs();
    if (cost[m][m] == INF2) printf("-1");
    else printf("%d", cost[m][m]);
    return 0;
}

最后一点数据：

100 1000
1 1 0
2 2 1
3 3 1
4 4 0
5 5 1
6 6 0
7 7 1
8 8 0
9 9 1
10 10 0
11 11 0
12 12 1
13 13 0
14 14 1
15 15 1
16 16 0
17 17 1
18 18 1
19 19 0
20 20 1
21 21 0
22 22 1
23 23 1
24 24 1
25 25 1
26 26 1
27 27 0
28 28 0
29 29 1
30 30 1
31 31 0
32 32 0
33 33 1
34 34 0
35 35 0
36 36 0
37 37 0
38 38 0
39 39 0
40 40 0
41 41 0
42 42 1
43 43 1
44 44 1
45 45 0
46 46 0
47 47 1
48 48 1
49 49 1
50 50 0
51 51 1
52 52 1
53 53 0
54 54 1
55 55 1
56 56 1
57 57 0
58 58 1
59 59 1
60 60 0
61 61 1
62 62 1
63 63 0
64 64 1
65 65 0
66 66 1
67 67 1
68 68 0
69 69 1
70 70 0
71 71 1
72 72 0
73 73 1
74 74 0
75 75 1
76 76 0
77 77 1
78 78 0
79 79 1
80 80 1
81 81 1
82 82 0
83 83 0
84 84 0
85 85 0
86 86 1
87 87 1
88 88 1
89 89 0
90 90 0
91 91 0
92 92 1
93 93 1
94 94 1
95 95 0
96 96 0
97 97 1
98 98 1
99 99 0
100 100 1
81 40 1
10 4 1
73 85 1
38 10 1
11 69 1
55 40 0
75 91 1
32 30 1
64 62 1
51 52 0
26 24 1
91 10 0
31 83 0
67 22 0
83 65 0
26 32 0
100 59 1
18 17 1
70 73 1
88 28 1
93 5 1
13 26 1
58 57 0
12 19 0
8 41 1
8 96 1
4 15 0
65 9 0
78 63 1
55 14 0
55 75 0
90 85 0
7 55 0
9 7 1
64 28 1
7 56 0
68 62 0
42 81 1
74 71 0
3 5 0
72 76 0
95 31 0
83 61 0
38 29 0
46 88 1
80 86 0
29 20 0
1 71 0
42 50 0
84 67 0
1 38 1
53 59 1
63 78 0
24 22 1
41 1 0
6 7 1
71 4 0
95 13 0
69 11 0
69 42 0
56 71 1
60 87 1
52 24 1
96 50 1
71 18 1
43 17 1
84 93 1
42 89 0
84 21 1
52 10 0
94 38 1
55 7 1
23 85 1
53 42 1
68 46 0
88 8 1
96 25 1
38 73 1
34 15 1
61 58 0
31 36 0
96 65 0
84 47 1
93 1 0
22 62 1
77 38 1
87 44 0
69 27 1
14 48 1
84 7 1
88 91 1
17 60 0
100 11 0
66 8 0
25 61 0
40 100 1
63 19 1
8 48 0
83 15 1
62 94 0
42 37 1
57 93 0
94 40 1
42 69 0
2 32 1
49 60 0
96 3 0
58 99 1
9 36 0
5 34 0
45 36 1
37 4 1
50 23 1
50 34 1
23 18 1
23 30 1
32 89 0
42 71 1
83 96 1
46 13 1
14 65 0
5 74 1
67 50 1
84 63 0
95 29 0
94 31 0
50 68 0
75 57 1
75 65 0
35 74 0
26 16 0
11 46 0
59 6 1
97 76 0
98 48 0
86 45 0
40 16 0
52 18 1
97 50 0
37 27 0
53 61 1
35 28 1
36 95 1
14 97 0
60 49 0
69 8 1
55 70 0
77 62 0
80 96 1
42 34 1
27 9 1
81 50 1
39 13 1
48 78 1
28 15 0
64 83 1
71 14 1
44 45 1
74 70 1
76 43 0
31 88 0
75 29 0
82 12 0
98 43 1
98 81 0
98 96 0
6 39 0
2 40 1
89 48 0
64 24 1
83 22 1
83 9 1
83 77 0
58 6 0
91 11 0
40 7 1
59 40 1
84 78 1
84 22 0
68 14 1
75 20 1
31 53 0
88 41 1
51 19 0
79 13 1
35 98 1
34 68 0
32 38 0
50 29 1
78 27 0
83 90 0
28 87 1
62 42 1
79 57 0
75 80 1
77 60 0
14 58 1
81 8 1
5 81 0
16 28 1
85 23 0
61 17 0
79 39 1
74 61 0
44 69 1
56 41 0
47 21 0
4 50 1
28 7 0
12 73 0
16 18 0
35 37 1
10 58 0
91 38 0
13 48 0
40 38 1
93 8 1
9 84 0
60 89 1
90 94 1
60 13 0
74 45 0
95 30 0
17 10 0
77 94 1
32 10 1
44 32 1
54 20 0
3 37 0
94 14 0
28 20 1
85 35 0
84 57 1
81 57 1
67 100 0
55 24 0
49 20 0
28 51 1
100 40 0
35 62 0
21 56 0
29 70 0
86 87 0
26 18 0
90 23 0
41 42 1
9 16 0
33 18 1
69 47 1
73 7 1
86 59 1
16 32 1
54 13 0
40 88 0
15 92 0
58 89 1
38 5 1
10 62 0
66 3 0
95 3 1
67 36 0
76 36 0
27 73 0
39 90 0
93 66 1
42 35 0
20 60 0
72 74 0
97 18 0
54 52 0
19 25 1
7 53 0
61 87 0
57 58 1
26 20 0
77 97 0
38 12 1
20 97 1
90 51 1
25 83 1
52 69 1
5 20 1
95 76 0
97 95 1
71 2 1
91 39 0
55 96 0
95 92 0
10 35 0
91 2 1
38 19 0
62 82 1
37 80 1
36 8 0
73 6 1
9 14 0
84 44 1
77 54 1
93 90 1
40 2 0
95 10 0
65 36 1
63 9 1
5 6 1
31 92 0
58 87 0
82 49 0
39 32 0
89 53 1
3 99 0
55 74 0
63 91 0
34 28 0
47 41 1
56 96 1
22 12 0
62 85 0
76 96 0
37 90 0
32 5 1
74 24 1
27 13 0
72 83 1
10 83 1
32 67 0
10 48 0
67 64 0
18 51 0
36 16 0
79 37 1
2 57 1
21 7 1
97 39 0
48 35 1
34 20 0
99 54 0
95 40 1
81 97 1
48 82 1
73 46 1
95 53 0
88 42 1
27 67 1
61 50 0
36 30 0
8 87 0
75 82 1
27 47 1
61 73 0
77 84 1
85 77 0
43 7 0
1 27 0
37 6 0
90 2 1
38 70 1
20 46 0
36 2 0
62 88 1
89 28 0
55 72 1
43 49 0
80 3 1
59 87 1
60 92 1
42 90 0
59 5 0
76 46 0
19 15 0
57 44 0
100 50 1
15 72 0
38 81 1
78 18 1
51 56 0
21 77 1
91 67 0
57 15 1
82 44 1
89 75 1
88 35 0
93 11 1
63 26 0
51 2 1
45 77 0
29 99 0
7 65 1
45 62 1
13 4 0
13 92 0
58 52 1
46 89 1
52 65 0
74 9 1
27 82 1
45 43 0
75 56 0
9 55 0
69 61 1
36 50 1
40 4 1
2 13 1
79 35 1
91 23 0
57 66 0
9 97 1
24 52 0
65 93 1
33 64 0
19 29 1
50 88 1
79 33 0
97 96 1
54 83 1
27 10 1
63 38 0
43 68 1
76 99 0
99 65 0
33 54 0
18 49 1
38 60 1
53 33 0
14 68 0
55 50 0
10 17 0
9 100 1
54 61 0
20 31 1
2 30 1
9 1 1
79 95 1
34 69 1
95 81 0
62 63 1
89 16 1
87 96 0
5 69 1
77 81 1
18 71 1
46 44 1
40 34 1
1 33 1
28 27 0
76 48 0
13 70 1
24 89 1
27 78 1
27 51 0
49 100 1
19 33 1
53 80 1
75 10 0
73 71 0
74 32 1
74 90 1
48 1 1
5 72 1
97 80 0
91 96 1
36 26 1
32 13 0
36 22 1
38 24 1
98 66 1
50 58 1
45 46 1
23 67 0
25 42 1
19 77 0
78 90 0
93 36 0
14 96 1
96 13 1
62 56 0
66 5 0
33 69 0
10 76 0
7 18 0
53 90 0
37 85 1
52 85 1
86 67 1
70 28 0
77 2 1
5 9 1
89 24 0
38 17 0
3 16 0
48 60 0
87 25 0
75 81 1
86 12 1
84 39 1
40 46 1
21 76 1
58 88 1
45 58 0
67 26 0
91 63 1
52 45 0
7 23 0
27 53 1
66 13 1
56 30 1
94 70 0
7 11 0
32 62 1
41 83 1
84 27 1
35 24 0
94 47 0
2 34 0
38 35 0
47 92 0
83 5 1
35 60 0
56 82 1
61 15 0
64 6 1
1 47 1
62 31 0
47 65 1
40 32 0
21 1 1
25 65 1
70 40 1
78 15 0
89 54 1
55 35 1
79 89 1
9 21 1
93 4 0
16 43 0
53 49 1
36 45 0
28 96 0
55 56 1
91 59 0
3 30 1
69 76 1
71 35 1
99 44 1
81 23 1
84 14 1
32 29 0
98 68 0
75 67 1
94 22 1
45 81 1
28 86 0
39 31 0
2 94 1
75 58 1
88 7 1
40 52 0
66 22 0
17 52 0
19 49 0
92 62 1
69 9 1
91 61 0
69 44 0
45 4 0
23 41 1
65 46 0
2 36 1
76 5 0
45 39 1
35 6 0
78 99 0
96 74 1
69 82 1
18 9 1
43 15 1
36 72 0
87 68 1
15 20 0
28 17 1
61 37 1
51 84 0
88 79 1
69 33 0
63 7 1
56 45 0
40 63 1
82 27 1
58 2 0
11 43 1
93 47 0
27 77 1
98 24 0
41 63 1
69 7 1
39 8 1
31 51 1
73 57 0
22 27 0
32 82 0
10 1 0
10 60 0
57 68 1
48 74 1
41 39 0
52 100 1
82 86 1
64 50 1
85 49 1
42 8 0
6 12 0
24 60 1
87 98 0
71 40 0
49 97 1
22 2 0
15 14 1
59 83 1
15 94 1
78 82 0
17 50 0
6 37 0
39 3 1
16 86 0
94 54 0
65 86 1
98 82 0
64 8 1
76 11 0
73 92 1
61 85 1
44 27 0
45 94 0
84 43 0
34 74 0
81 82 0
10 96 1
48 13 0
46 52 1
87 12 0
52 74 1
65 21 0
83 78 0
93 16 1
63 66 0
7 83 0
29 75 1
37 96 0
93 96 1
18 19 0
48 87 0
83 75 0
37 10 0
33 76 1
82 15 1
36 55 0
9 30 0
59 26 0
14 23 1
8 52 0
3 78 1
8 85 0
85 81 0
64 99 0
64 12 0
76 69 0
63 36 0
89 73 0
25 20 1
97 27 1
3 33 0
12 39 0
48 96 1
21 81 1
17 12 0
23 32 0
81 73 1
71 68 1
87 72 0
31 15 1
66 21 0
100 68 0
73 48 1
24 65 0
56 76 0
15 36 1
19 17 0
45 2 0
57 33 1
90 40 0
48 36 1
11 8 1
6 53 0
66 18 0
80 53 0
8 33 0
54 37 1
82 42 0
66 69 1
88 56 1
74 67 0
87 7 1
8 65 1
79 38 1
1 65 0
27 7 1
93 35 0
54 62 0
90 86 1
64 5 1
45 68 0
59 36 1
62 87 1
88 96 1
76 88 1
70 17 0
38 45 0
1 75 1
74 6 1
25 11 1
93 3 1
6 26 0
50 33 1
94 82 0
3 22 0
60 45 1
93 99 0
11 37 1
8 6 0
83 49 1
91 33 1
25 13 0
53 40 1
76 98 1
64 57 1
45 91 0
88 22 0
46 72 1
39 83 1
72 39 0
61 60 0
63 43 1
94 95 0
43 76 1
73 21 0
43 36 0
27 28 1
59 52 1
99 78 0
92 28 0
93 24 1
83 25 0
36 27 0
62 49 1
98 17 0
57 60 0
34 36 0
84 77 0
67 35 1
16 53 0
18 83 1
60 21 0
36 63 0
26 67 0
81 18 1
45 67 1
60 74 1
90 81 0
17 93 0
68 69 0
4 43 0
32 21 1
49 72 1
37 49 1
89 36 1
2 76 0
41 6 0
44 15 0
4 20 1
69 10 0
41 11 1
74 19 0
22 57 1
65 72 0
55 85 1
72 75 1
66 32 1
47 19 0
56 53 0
19 3 0
95 78 1
81 13 1
82 59 0
30 17 1
16 83 0
18 45 0
45 14 0
23 8 1
15 11 1
89 95 1
100 8 1
4 63 0
96 37 0
40 1 1
36 38 0
38 56 0
48 18 1
52 38 0
85 82 0
75 49 0
62 10 1
26 77 0
45 69 1
21 66 0
84 70 0
87 80 1
61 29 1
74 43 1
68 76 1
96 7 0
16 60 1
51 42 0
50 87 0
91 76 1
20 73 0
57 51 1
93 51 0
6 85 0
37 95 0
70 99 0
59 12 0
60 52 1
77 66 1
76 45 1
97 99 1
5 3 1
8 53 0
59 31 0
82 68 1
38 55 1
92 82 0
56 17 0
7 20 1
57 28 0
75 76 1
47 79 1
27 88 1
77 48 1
82 90 0
90 77 1
61 25 1
99 52 0
7 45 1
81 46 1
36 70 0
35 20 0
54 35 0
63 87 1
90 28 0
32 75 0
22 75 0
89 57 1
14 93 1
70 50 1
11 54 1
60 78 1
83 4 0
16 61 0
5 33 0
5 88 1
96 8 0
81 84 1
3 62 0
59 37 1
87 3 1
10 39 1
90 64 0
81 83 1
48 94 0
93 33 0
92 12 0
21 24 1
48 70 1
22 32 0
81 88 0
70 66 1
19 13 0
99 32 0
38 31 0
18 68 0
22 61 1
92 16 1
10 44 1
40 5 0
32 4 0
92 79 1
77 88 0
99 41 0
57 78 1
44 13 0
81 89 0

215