class Weigthed_Digraph: #入力定義 def __init__(self,vertex=[]): self.vertex=set(vertex) self.edge_number=0 self.vertex_number=len(vertex) self.adjacent_out={v:{} for v in vertex} #出近傍(vが始点) self.adjacent_in={v:{} for v in vertex} #入近傍(vが終点) #頂点の追加 def add_vertex(self,*adder): for v in adder: if v not in self.vertex: self.adjacent_in[v]={} self.adjacent_out[v]={} self.vertex_number+=1 self.vertex.add(v) #辺の追加(更新) def add_edge(self,From,To,weight=1): for v in [From,To]: if v not in self.vertex: self.add_vertex(v) if To not in self.adjacent_in[From]: self.edge_number+=1 self.adjacent_out[From][To]=weight self.adjacent_in[To][From]=weight #辺を除く def remove_edge(self,From,To): for v in [From,To]: if v not in self.vertex: self.add_vertex(v) if To in self.adjacent_out[From]: del self.adjacent_out[From][To] del self.adjacent_in[To][From] self.edge_number-=1 #頂点を除く def remove_vertex(self,*vertexes): for v in vertexes: if v in self.vertex: self.vertex_number-=1 for u in self.adjacent_out[v]: del self.adjacent_in[u][v] self.edge_number-=1 del self.adjacent_out[v] for u in self.adjacent_in[v]: del self.adjacent_out[u][v] self.edge_number-=1 del self.adjacent_in[v] #Walkの追加 def add_walk(self,*walk): pass #Cycleの追加 def add_cycle(self,*cycle): pass #頂点の交換 def __vertex_swap(self,p,q): self.vertex.sort() #グラフに頂点が存在するか否か def vertex_exist(self,v): return v in self.vertex #グラフに辺が存在するか否か def edge_exist(self,From,To): if not(self.vertex_exist(From) and self.vertex_exist(To)): return False return To in self.adjacent_out[From] #近傍 def neighbohood(self,v): if not self.vertex_exist(v): return [] return list(self.adjacent[v]) #出次数 def out_degree(self,v): if not self.vertex_exist(v): return 0 return len(self.adjacent_out[v]) #入次数 def in_degree(self,v): if not self.vertex_exist(v): return 0 return len(self.adjacent_in[v]) #次数 def degree(self,v): if not self.vertex_exist(v): return 0 return self.out_degree(v)-self.in_degree(v) #頂点数 def vertex_count(self): return len(self.vertex) #辺数 def edge_count(self): return self.edge_number #頂点vを含む連結成分 def connected_component(self,v): pass #Dijkstra def Dijkstra(D,From,To,with_path=False): """Dijksta法を用いて,FromからToまでの距離を求める. D:辺の重みが全て非負の有向グラフ From:始点 To:終点 with_path:最短路も含めて出力するか? (出力の結果) with_path=True->(距離,最短経路の辿る際の前の頂点) with_path=False->距離 """ from copy import copy from heapq import heappush,heappop T={v:float("inf") for v in D.vertex} T[From]=0 if with_path: Prev={v:None for v in D.vertex} Q=[(0,From)] Flag=False while Q: c,u=heappop(Q) if u==To: Flag=True break if T[u]T[u]+D.adjacent_out[u][v]: T[v]=T[u]+D.adjacent_out[u][v] heappush(Q,(T[v],v)) if with_path: Prev[v]=u if not Flag: if with_path: return (float("inf"),None) else: return float("inf") if with_path: path=[To] u=To while (Prev[u]!=None): u=Prev[u] path.append(u) return (T[To],path[::-1]) else: return T[To] #================================================ from itertools import chain N,M=map(int,input().split()) F=[[0]*(N+1) for _ in range(N+1)] for _ in range(M): h,w,c=map(int,input().split()) F[h][w]=c V=[(i,j,m) for i in range(1,N+1) for j in range(1,N+1) for m in [0,1]] E=[(1,0),(-1,0),(0,1),(0,-1)] D=Weigthed_Digraph(V) for i in range(1,N+1): for j in range(1,N+1): for (a,b) in E: if 1<=i+a<=N and 1<=j+b<=N: print(i,j,) D.add_edge((i,j,0),(i+a,j+b,0),1+F[i+a][j+b]) D.add_edge((i,j,1),(i+a,j+b,1),1+F[i+a][j+b]) D.add_edge((i,j,0),(i+a,j+b,1),1) alpha=Dijkstra(D,(1,1,0),(N,N,0),False) beta =Dijkstra(D,(1,1,0),(N,N,1),False) print(min(alpha,beta))