from math import inf
import heapq
from collections import defaultdict
"""
Dijkstra算法
构建邻接表graph
构建用来储存到起点最短长度的列表dict,用来存储需要加入判断的边的最小堆heap
整体思路:不断地去更新从起点到邻接点的最短距离
从起点(第一个发散点)开始,更新其邻接点到起点的距离
并将更新过(如果新的路径距离更短)的点和距离(到起点的最短距离)放入heap中
heap中放置的是与能与发散点集相连的所有点,以及这些点与起点的最短距离(存在部分不是最短距离的)
找到距离起点最近的点(heap中的)成为新的发散点
更新其邻接点到起点的最短距离
找到所有进入heap中的最短距离对应的点,成为新的发散点
如此循环,直到heap为空
heap为空意味着,所有点到起点的最短距离已经更新完毕
因为如果还有需要更新的点,那么heap就会加入新的元素,不会为空
此时dict中放置着从起点到达各个点的最短距离
注意,heap中的点可能会重复
比如:[1,3,3],[1,2,1],[2,3,1]
heap的发展为[(0,1)]→[(1,2),(3,3)]→[(3,3)]→[(2,3),(3,3)]
此时heap中重复出现点3
所有要进行剪枝,即如果当前d!=dict[node],即当前距离不是最短距离,则逃过这个元素,操作heap中的下一个元素
"""
n,m = map(int,input().split())
graph = defaultdict(list)
for _ in range(m):
    u,v,w = map(int,input().split())
    graph[u].append((v,w))
    graph[v].append((u,w))
dist = [inf]*(5001)
dist[1] = 0
heap = [(0,1)]
while heap:
    d,node = heapq.heappop(heap)
    if d != dist[node]:
        continue
    for neighbor,w in graph[node]:
        new_dist = d + w
        if new_dist < dist[neighbor]:
            dist[neighbor] = new_dist
            heapq.heappush(heap,(new_dist,neighbor))

print(dist[n] if dist[n]!=inf else -1)