class Graph:

    def __init__(self, n, directed=False, decrement=True, edges=[]):
        self.n = n
        self.directed = directed
        self.decrement = decrement
        self.edges = [[] for _ in range(self.n)]
        for x, y, cost in edges:
            self.add_edge(x, y, cost)

    def add_edge(self, x, y, cost):
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].append((y, cost))
        if self.directed == False:
            self.edges[y].append((x, cost))

    def dijkstra(self, start=None, INF=10**18):
        """
        返り値は 0-indexed !!!
        :param start: スタート地点
        :return: スタート地点から各点への距離のリスト
        備考: heqpq の比較のための key は第一引数である点に注意( = heappush(heapq, (key,value)) )
        """
        res = [INF] * self.n
        if start is None: start=self.decrement
        start=start-self.decrement
        res[start] = 0
        next_set = [(0, start)]
        while next_set:
            dist, p = heappop(next_set)
            if res[p] < dist:
                continue
            """ここで頂点pまでの最短距離が確定。よって、ここを通るのはN回のみ"""
            for q, cost in self.edges[p]:
                temp_d = dist + cost
                if temp_d < res[q]:
                    res[q] = temp_d
                    heappush(next_set, (temp_d, q))

        return res

    def draw(self):
        """
        :return: グラフを可視化
        """
        import matplotlib.pyplot as plt
        import networkx as nx

        if self.directed:
            G = nx.DiGraph()
        else:
            G = nx.Graph()
        for x in range(self.n):
            for y, cost in self.edges[x]:
                G.add_edge(x + self.decrement, y + self.decrement, weight=cost)


        edge_labels = {(i, j): w['weight'] for i, j, w in G.edges(data=True)}
        pos = nx.spring_layout(G)
        nx.draw_networkx(G, pos, with_labels=True, connectionstyle='arc3, rad = 0.1')
        nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
        plt.axis("off")
        plt.show()

#########################################################
def example():
    global input
    example = iter(
        """
3 1
2 2 3
        """
            .strip().split("\n"))
    input = lambda: next(example)



#########################################################
import sys
from heapq import *
input = sys.stdin.readline

# example()

INF = 10**18  # 大きい数字

N,M = map(int, input().split())

graph = Graph(N**2, directed=True, decrement=False)

mat=[[0]*N for _ in range(N)]
for _ in range(M):
    h,w,c=map(int, input().split())
    h-=1
    w-=1
    mat[h][w]=c

for h0 in range(N):
    for w0 in range(N):
        for dh,dw in ((-1,0),(1,0),(0,-1),(0,1)):
            h,w=h0+dh,w0+dw
            if 0<=h<N and 0<=w<N:
                graph.add_edge(h0*N+w0,h*N+w,1+mat[h][w])

dist0=graph.dijkstra(start=0,INF=INF)
dist1=graph.dijkstra(start=N**2-1,INF=INF)

d=INF
for h in range(N):
    for w in range(N):
        d=min(dist0[h*N+w]+dist1[h*N+w]-2*mat[h][w],d)
print(d)