import sys readline = sys.stdin.readline from heapq import heappush, heappop inf = float('inf') def dijkstra(s, g, N): # ゴールがない場合はg=-1とする。 g0 = f(N-1, N-1, 0) g1 = f(N-1, N-1, 1) def cost(v, m): return v * N + m dist = [inf] * N mindist = [inf] * N seen = [False] * N Q = [cost(0, s)] while Q: c, m = divmod(heappop(Q), N) if seen[m]: continue seen[m] = True dist[m] = c if m == g0 or m == g1: return dist #------heapをアップデートする。-------- for u, C in G[m]: if seen[u]: continue newdist = dist[m] + C #------------------------------------ if newdist >= mindist[u]: continue mindist[u] = newdist heappush(Q, cost(newdist, u)) return dist def f(h, w, c): return h + N * w + N * N * c N, M = map(int, readline().split()) temp = [[0] * N for i in range(N)] for i in range(M): h, w, c = map(int, readline().split()) h, w = h - 1, w - 1 temp[h][w] = c G = [[] for i in range(N * N * 2)] dx = [1, 0, -1, 0] dy = [0, 1, 0, -1] for i in range(N): for j in range(N): for k in range(4): x = i + dx[k] y = j + dy[k] if x < 0 or x > N - 1 or y < 0 or y > N - 1: continue G[f(i, j, 0)].append( ( f(x, y, 0), temp[x][y] + 1)) G[f(x, y, 0)].append( ( f(i, j, 0), temp[i][j] + 1)) G[f(i, j, 1)].append( ( f(x, y, 1), temp[x][y] + 1)) G[f(x, y, 1)].append( ( f(i, j, 1), temp[i][j] + 1)) G[f(i, j, 0)].append( ( f(x, y, 1), 1)) G[f(x, y, 0)].append( ( f(i, j, 1), 1)) D = dijkstra(0, f(N - 1, N - 1, 1), N * N * 2) print(min(D[f(N - 1, N - 1, 0)], D[f(N - 1, N - 1, 1)]))