from typing import List, Tuple
from queue import PriorityQueue

'''
迪杰特斯拉算法求解单源最短路问题, 有向图和无向图均可求解
'''


class DijkStra:
    # start_node 是单源最短路起点 edges是边的三元组(节点1， 节点2， 边权重) nodes是所有节点的列表
    def __init__(self, start_node, edges: List[Tuple[int, int, int]], nodes: List[int], is_directed = False):
        self.edges = edges
        self.nodes = nodes
        self.start_node = start_node
        self.is_directed = is_directed

    def __init(self):
        edges = self.edges
        nodes = self.nodes
        start_node = self.start_node

        self.link = {node: {} for node in nodes}  # 邻接表
        self.start_node = start_node
        self.S = {}  # 已经确定最短路径长度的节点集合
        self.total_nodes_num = len(nodes)
        U = {node: 0x7fffffff for node in nodes if node != start_node}  # 还未确定最短路径长度的节点集合
        U[start_node] = 0

        for a, b, edge_len in edges:
            self.link[a][b] = edge_len
            if not self.is_directed:
                self.link[b][a] = edge_len

            if a == start_node:
                U[b] = edge_len

            if not self.is_directed:
                if b == start_node:
                    U[a] = edge_len

        self.U_que = PriorityQueue()  # 维护U集合的小顶堆，堆里面的内容是(路径长度， 节点值)的二元组
        for k, v in U.items():
            self.U_que.put((v, k))


    # 获取最短路径长度的列表[(节点1，长度1), (节点2, 长度2) .....]
    def getMinPathLen(self) -> List[Tuple[int, int]]:
        return self.getMinInfo(False)

    # 获取所有最短路径列表[(节点1, 长度1, 路径节点列表1)， (节点2, 长度2, 路径节点列表2)]
    def getMinPath(self):
        return self.getMinInfo(True)

    def getMinInfo(self, get_path):
        self.__init()
        pre = {}  # 记录每个节点结尾的最短路径的前驱节点

        while len(self.S) != self.total_nodes_num:
            while True:
                min_edge_len, min_node = self.U_que.get_nowait()  # 从U中把当前路径长度最小的节点取出来
                if min_node not in self.S:
                    break

            self.S[min_node] = min_edge_len

            # 更新U集合中节点的距离
            for next in self.link[min_node]:
                if next not in self.S:
                    if next not in pre or min_edge_len + self.link[min_node][next] < self.S[pre[next]] + self.link[pre[next]][next]:
                        self.U_que.put_nowait((min_edge_len + self.link[min_node][next], next))
                        pre[next] = min_node

        # 生成路径函数
        def __getPath(end_node):
            stack = []
            node = end_node
            while True:
                stack.append(node)
                if node not in pre:
                    break
                node = pre[node]
            return stack[::-1]

        return [(k, v, __getPath(k)) for k, v in self.S.items()] if get_path else [(k, v) for k, v in self.S.items()]

n, m = map(int, input().split())
nodes = [i for i in range(1, n+1)]
edges = {}
for _ in range(m):
    a, b, w = map(int, input().split())
    if (a, b) not in edges:
        edges[(a, b)] = w
    else:
        edges[(a, b)] = min(edges[(a, b)], w)

edges = [(a, b, w) for (a, b), w in edges.items()]

algo = DijkStra(1, edges, nodes, is_directed = True)
ans = algo.getMinPathLen()
for k, v in ans:
    if k == n:
        print(v if v != 0x7fffffff else -1)
        break