def main(): import sys,heapq input=sys.stdin.readline N,M=map(int,input().split()) inf=float("inf") F=[[1]*(N+1) for _ in range(N+1)] for _ in range(M): h,w,c=map(int,input().split()) F[h][w]+=c V=[(1,0),(-1,0),(0,1),(0,-1)] Dist0=[[inf]*(N+1) for __ in range(N+1)] Dist1=[[inf]*(N+1) for __ in range(N+1)] Dist0[1][1]=0 Q=[(0,(1,1,0))] heapq.heapify(Q) while Q: d,v=heapq.heappop(Q) i,j,m=v if (m==0 and d<Dist0[i][j]) or (m==1 and d<Dist1[i][j]): continue if i==j==N: break for (a,b) in V: if 1<=i+a<=N and 1<=j+b<=N: c=d+F[i+a][j+b] if m==0 and c<Dist0[i+a][j+b]: Dist0[i+a][j+b]=c heapq.heappush(Q,(c,(i+a,j+b,0))) if m==1 and c<Dist1[i+a][j+b]: Dist1[i+a][j+b]=c heapq.heappush(Q,(c,(i+a,j+b,1))) if m==0 and d+1<Dist1[i+a][j+b]: Dist1[i+a][j+b]=d+1 heapq.heappush(Q,(d+1,(i+a,j+b,1))) print(min(Dist0[N][N],Dist1[N][N])) if __name__=="__main__": main()