import heapq
N,M = map(int,input().split())
C = [[0 for _ in range(N+1)] for _ in range(N+1)]
A = []
for _ in range(M):
    h,w,c = map(int,input().split())
    C[h][w] = c
    A.append((h,w))
INFTY = 10**12+10000
ans = INFTY
for h,w in A:
    c0 = C[h][w]
    C[h][w] = 0
    dist = [[INFTY for _ in range(N+1)] for _ in range(N+1)]
    dist[1][1] = 0
    visited = [[False for _ in range(N+1)] for _ in range(N+1)]
    heap = [(0,1,1)]
    while heap:
        d,i,j = heapq.heappop(heap)
        if dist[i][j]<d:continue
        visited[i][j] = True
        for di,dj in [[0,1],[-1,0],[0,-1],[1,0]]:
            if 1<=i+di<=N and 1<=j+dj<=N and visited[i+di][j+dj]==False and dist[i+di][j+dj]>d+1+C[i+di][j+dj]:
                dist[i+di][j+dj] = d+1+C[i+di][j+dj]
                heapq.heappush(heap,(d+1+C[i+di][j+dj],i+di,j+dj))
    ans = min(ans,dist[N][N])
    C[h][w] = c0
print(ans)