n,m=map(int,input().split())
from collections import deque
dp=[[[10**18,10**18] for i in range(n+10)] for j in range(n+10)]
dp[1][1][0]=0
seki=[[0]*(n+10) for i in range(n+10)]

for i in range(m):
    h,w,c=map(int,input().split())
    seki[h][w]=c

data=deque([[1,1]])
while len(data)>0:
    now=data.pop()
    h,w=now[0],now[1]
    if 2<=h:
        f=0
        if seki[h-1][w]==0:
            if dp[h-1][w][0]>dp[h][w][0]+1:
                dp[h-1][w][0]=dp[h][w][0]+1
                f=1
            if dp[h-1][w][1]>dp[h][w][1]+1:
                dp[h-1][w][1]=dp[h][w][1]+1
                f=1
        else:
            if dp[h-1][w][0]>dp[h][w][0]+1+seki[h-1][w]:
                dp[h-1][w][0]=dp[h][w][0]+1+seki[h-1][w]
                f=1
            if dp[h-1][w][1]>dp[h][w][1]+1+seki[h-1][w]:
                dp[h-1][w][1]=dp[h][w][1]+1+seki[h-1][w]
                f=1

            if dp[h-1][w][1]>dp[h][w][0]+1:
                dp[h-1][w][1]=dp[h][w][0]+1
                f=1
        if f:
            data.append([h-1,w])

    if 2 <= w:
        f = 0
        if seki[h ][w-1] == 0:
            if dp[h ][w-1][0] > dp[h][w][0] + 1:
                dp[h ][w-1][0] = dp[h][w][0] + 1
                f = 1
            if dp[h ][w-1][1] > dp[h][w][1] + 1:
                dp[h ][w-1][1] = dp[h][w][1] + 1
                f = 1
        else:
            if dp[h ][w-1][0] > dp[h][w][0] + 1 + seki[h ][w-1]:
                dp[h ][w-1][0] = dp[h][w][0] + 1 + seki[h ][w-1]
                f = 1
            if dp[h ][w-1][1] > dp[h][w][1] + 1 + seki[h ][w-1]:
                dp[h ][w-1][1] = dp[h][w][1] + 1 + seki[h ][w-1]
                f = 1

            if dp[h ][w-1][1] > dp[h][w][0] + 1:
                dp[h ][w-1][1] = dp[h][w][0] + 1
                f = 1
        if f:
            data.append([h , w-1])

    if  h<=n-1:
        f = 0
        if seki[h + 1][w] == 0:
            if dp[h + 1][w][0] > dp[h][w][0] + 1:
                dp[h + 1][w][0] = dp[h][w][0] + 1
                f = 1
            if dp[h + 1][w][1] > dp[h][w][1] + 1:
                dp[h + 1][w][1] = dp[h][w][1] + 1
                f = 1
        else:
            if dp[h + 1][w][0] > dp[h][w][0] + 1 + seki[h + 1][w]:
                dp[h + 1][w][0] = dp[h][w][0] + 1 + seki[h + 1][w]
                f = 1
            if dp[h + 1][w][1] > dp[h][w][1] + 1 + seki[h + 1][w]:
                dp[h + 1][w][1] = dp[h][w][1] + 1 + seki[h + 1][w]
                f = 1

            if dp[h + 1][w][1] > dp[h][w][0] + 1:
                dp[h + 1][w][1] = dp[h][w][0] + 1
                f = 1
        if f:
            data.append([h + 1, w])

    if n-1>=w:
        f = 0
        if seki[h ][w+1] == 0:
            if dp[h ][w+1][0] > dp[h][w][0] + 1:
                dp[h ][w+1][0] = dp[h][w][0] + 1
                f = 1
            if dp[h ][w+1][1] > dp[h][w][1] + 1:
                dp[h ][w+1][1] = dp[h][w][1] + 1
                f = 1
        else:
            if dp[h ][w+1][0] > dp[h][w][0] + 1 + seki[h ][w+1]:
                dp[h ][w+1][0] = dp[h][w][0] + 1 + seki[h ][w+1]
                f = 1
            if dp[h ][w+1][1] > dp[h][w][1] + 1 + seki[h ][w+1]:
                dp[h ][w+1][1] = dp[h][w][1] + 1 + seki[h ][w+1]
                f = 1

            if dp[h ][w+1][1] > dp[h][w][0] + 1:
                dp[h ][w+1][1] = dp[h][w][0] + 1
                f = 1
        if f:
            data.append([h , w+1])

print(min(dp[n][n]))