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)