import heapq

def shortest_path(G, start, end):
   def flatten(L):       # Flatten linked list of form [0,[1,[2,[]]]]
      while len(L) > 0:
         yield L[0]
         L = L[1]

   q = [(0, start, ())]  # Heap of (cost, path_head, path_rest).
   visited = set()       # Visited vertices.
   while True:
      (cost, v1, path) = heapq.heappop(q)
      if v1 not in visited:
         visited.add(v1)
         if v1 == end:
            #print cost
            return list(flatten(path))[::-1] + [v1],cost
         path = (v1, path)
         for (v2, cost2) in G[v1].iteritems():
            if v2 not in visited:
               heapq.heappush(q, (cost + cost2, v2, path))


def remove_node(graph, key):
    for k,v in graph.items():
        #print v
        #for edges in v:
        for n,w in v.items():
            if n==key:
                del v[n]
    return graph



n,e = [int(i) for i in raw_input().spit(' ')]
graph={}
for i in xrange(1,n+1):
    graph[i]={}

for j in xrange(e):
    v1,v2,w = raw_input().split(' ')
    graph[v1][v2] = int(w)
    graph[v2][v1] = int(w)



path1,cost1 = shortest_path(graph,'1',n)
path = path1
path1 = path1[1:-1]

for item in path1:
    gp1=remove_node(graph,item)
for item in path1:
    del gp1[item]

path2,cost2 = shortest_path(graph,n,'1')

print cost1+cost2

raw_input()