Inf = 999999
#Dijkstra算法是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题
#核心思想是：每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。
def Dijkstra(start, end):
#未访问过的顶点集合
queue={i:Inf for i in range(start+1,n+1)}
#显而易见，起点到起点到距离为0
dist[start] = 0
while start is not end :
#存储当前结点的所有邻接节点，例如，1的邻接节点是2和8
pos = [i for i in range(1,n+1) if map[start][i] < Inf]
#更新邻接节点到始点距离
for i in pos:
#更新这些路径到达起点的位置，可能之前有路径到达过此结点
dist[i] = min(dist[i], dist[start] + map[start][i])
#更新剩余结点到起点到距离
if i in queue: queue[i]= dist[i]
#在未访问过的顶点集合中选择一条距离起点最近到顶点，前行
start = min(queue,key = queue.get)
#用弹出队列到方式标记 最短路径
queue.pop(start)
#我们此时来到了下一个顶点，后面就是重复之前到过程，我们加快速度
return -1 if dist[end] is Inf else dist[end]
if __name__ == "__main__":
n, m = [int(i) for i in input().split(" ")]
# 初始化个点到起点到距离
map = [[Inf for _ in range(n + 1)] for _ in range(n + 1)]
dist = [Inf for _ in range(n + 1)]
for _ in range(m):
u, v, d = [int(x) for x in input().split(" ")]
map[u][v] = map[v][u] = d
print(Dijkstra(1, 5))
