from heapq import heappop, heappush INF = 10 ** 15 N, M = map(int, input().split()) c = [[0] * N for _ in range(N)] for _ in range(M): h, w, cc = map(int, input().split()) c[h - 1][w - 1] = cc dp0 = [[INF] * N for _ in range(N)] dp1 = [[INF] * N for _ in range(N)] dp0[0][0] = 0 q = [(0, 0, 0, 0)] while q: cc, h, w, t = heappop(q) if t == 0: if dp0[h][w] < cc: continue if h != 0: nh = h - 1 nw = w if dp0[nh][nw] > dp0[h][w] + 1 + c[nh][nw]: dp0[nh][nw] = dp0[h][w] + 1 + c[nh][nw] heappush(q, (dp0[nh][nw], nh, nw, 0)) if dp1[nh][nw] > dp0[h][w] + 1: dp1[nh][nw] = dp0[h][w] + 1 heappush(q, (dp1[nh][nw], nh, nw, 1)) if h != N - 1: nh = h + 1 nw = w if dp0[nh][nw] > dp0[h][w] + 1 + c[nh][nw]: dp0[nh][nw] = dp0[h][w] + 1 + c[nh][nw] heappush(q, (dp0[nh][nw], nh, nw, 0)) if dp1[nh][nw] > dp0[h][w] + 1: dp1[nh][nw] = dp0[h][w] + 1 heappush(q, (dp1[nh][nw], nh, nw, 1)) if w != 0: nh = h nw = w - 1 if dp0[nh][nw] > dp0[h][w] + 1 + c[nh][nw]: dp0[nh][nw] = dp0[h][w] + 1 + c[nh][nw] heappush(q, (dp0[nh][nw], nh, nw, 0)) if dp1[nh][nw] > dp0[h][w] + 1: dp1[nh][nw] = dp0[h][w] + 1 heappush(q, (dp1[nh][nw], nh, nw, 1)) if w != N - 1: nh = h nw = w + 1 if dp0[nh][nw] > dp0[h][w] + 1 + c[nh][nw]: dp0[nh][nw] = dp0[h][w] + 1 + c[nh][nw] heappush(q, (dp0[nh][nw], nh, nw, 0)) if dp1[nh][nw] > dp0[h][w] + 1: dp1[nh][nw] = dp0[h][w] + 1 heappush(q, (dp1[nh][nw], nh, nw, 1)) elif t == 1: if dp1[h][w] < cc: continue if h != 0: nh = h - 1 nw = w if dp1[nh][nw] > dp1[h][w] + 1 + c[nh][nw]: dp1[nh][nw] = dp1[h][w] + 1 + c[nh][nw] heappush(q, (dp1[nh][nw], nh, nw, 1)) if h != N - 1: nh = h + 1 nw = w if dp1[nh][nw] > dp1[h][w] + 1 + c[nh][nw]: dp1[nh][nw] = dp1[h][w] + 1 + c[nh][nw] heappush(q, (dp1[nh][nw], nh, nw, 1)) if w != 0: nh = h nw = w - 1 if dp1[nh][nw] > dp1[h][w] + 1 + c[nh][nw]: dp1[nh][nw] = dp1[h][w] + 1 + c[nh][nw] heappush(q, (dp1[nh][nw], nh, nw, 1)) if w != N - 1: nh = h nw = w + 1 if dp1[nh][nw] > dp1[h][w] + 1 + c[nh][nw]: dp1[nh][nw] = dp1[h][w] + 1 + c[nh][nw] heappush(q, (dp1[nh][nw], nh, nw, 1)) print(min(dp0[N - 1][N - 1], dp1[N - 1][N - 1]))