n, m = map(int, input().split())
maxdist = float("inf")
g = [[maxdist] * (n+1) for _ in range(n+1)] # 由于是密集图，m>>n，因此用邻接矩阵来存储，g[x][y]表示x指向y的距离
d = [maxdist] * (n+1) # 存储每个点距离起点的距离，初始化为距离最大，d[1]=0
st = [False] * (n+1) # 判断某一点的最短距离是否已经确定，False表示未确定，True表示确定

def dijkstra():
    d[1] = 0
    for i in range(1, n+1): # 因为要确定n个点的最短路，因此要循环n次
        t = -1
        for j in range(1, n+1): # 每次找到还未确定最短路的点中距离起点最短的点t
            if not st[j] and (t==-1 or d[t]>d[j]):
                t = j
        st[t] = True
        for j in range(1, n+1): # 用t来更新t所指向的点的距离
            d[j] = min(d[j], d[t] + g[t][j])
    if d[n] >= maxdist:
        return -1
    else:
        return d[n]

for _ in range(m):
    x, y, z = map(int, input().split())
    g[x][y] = min(g[x][y], z) # 当出现重边时，只需取两个距离中的最小值
print(dijkstra())