def main(): import sys from heapq import heappush,heappop input = sys.stdin.readline N, M = map(int, input().split()) cost = [[0 for _ in range(N)] for _ in range(N)] for i in range(M): h, w, c = map(int, input().split()) h-=1;w-=1 cost[h][w] = c dis1 = [[float('inf') for _ in range(N)] for _ in range(N)] dis2 = [[float('inf') for _ in range(N)] for _ in range(N)] dis1[0][0] = 0 dis2[0][0] = 0 p = [(0,0,0,0)] xx = [0,1,0,-1] yy = [1,0,-1,0] while p: c, x, y, f = heappop(p) if f==0 and dis1[x][y]cost1: dis2[cx][cy] = cost1 heappush(p, (cost1, cx, cy, f)) else: if dis1[cx][cy]>cost1: dis1[cx][cy] = cost1 heappush(p, (cost1, cx, cy, f)) if dis2[cx][cy]>cost2: dis2[cx][cy] = cost2 heappush(p, (cost2, cx, cy, f+1)) print(min(dis1[-1][-1],dis2[-1][-1])) if __name__=='__main__': main()