"""
# 朴素版的Dijkstra算法的模板
n, m = map(int, input().split())
st = [False for i in range(n+1)]    # 存储当前已经确定最短距离点的集合
graph = [[float("inf") for i in range(n+1)] for j in range(n+1)]    # 邻接矩阵存稠密图

def dijkstra():
    dist = [float("inf") for i in range(n+1)]    # 存储每个点到节点1的最短距离
    dist[1] = 0
#     st[1] = True    # ！！！出错：应该放到下一行的循环里，去寻找与节点1距离最近的点，否则第一轮循环找到的t=2，而dist[2]是正无穷

    for i in range(1, n+1):
        t = 0    # 在还未确定最短路的点的集合中，寻找距离最小的点
        for j in range(1, n+1):
            if st[j]==False and ((t==0) or dist[j]<dist[t]):
                t = j
        st[t] = True

        # 用t更新其他点的距离
        for j in range(1, n+1):
            if dist[j]>dist[t]+graph[t][j]:
                dist[j] = dist[t]+graph[t][j]
    # 判断并返回
    if dist[n]==float("inf"):
        return -1
    else:
        return dist[n]
"""
# @pysnooper.snoop()
def dijkstra():
    dist = [float("inf") for i in range(n+1)]    # 存储每个点到节点1的最短距离
    dist[1] = 0
#     st[1] = True    # ！！！出错：应该放到下一行的循环里，去寻找与节点1距离最近的点，否则第一轮循环找到的t=2，而dist[2]是正无穷
    for i in range(1, n+1):
        t = 0    # 在还未确定最短路的点的集合中，寻找距离最小的点
        for j in range(1, n+1):
            if st[j]==False and ((t==0) or dist[j]<dist[t]):
                t = j
        st[t] = True
        # 用t更新其他点的距离
        for j in range(1, n+1):
            if dist[j]>dist[t]+graph[t][j]:
                dist[j] = dist[t]+graph[t][j]
    if dist[n]==float("inf"):
        return -1
    else:
        return dist[n]

# 1. 输入示例
n, m = map(int, input().split())
st = [False for i in range(n+1)]    # 存储当前已经确定最短距离点的集合

graph = [[float("inf") for i in range(n+1)] for j in range(n+1)]    # 邻接矩阵存稠密图
for i in range(m):
    x,y,z = map(int, input().split())
    graph[x][y] = min(graph[x][y], z)    # 处理重边：保留重边中权重最小的边
for i in range(1, n+1):    # 处理自环：正权边的自环一定不是最短路，所以初始化i到i的权重为0
    graph[i][i] = 0

res = dijkstra()
print(res)