n, m = map(int, input().split())

## 保存是否访问
st = [False for i in range(n+1)]

## graph 稠密图 用矩阵
g = [[float("inf") for i in range(n+1)] for i in range(n+1)]

## 离源点距离 初始化为正无穷，源点初始化为0
dist = [float("inf") for i in range(n+1)]
dist[1] = 0

## 读入边长， 注意有重边 所以只要保持最短的那个就好
for i in range(m):
    a, b, c = map(int, input().split())
    g[a][b] = min(g[a][b], c)

def dijkstra():
    ## 一次循环加入一个点到已确定最短路径长度的集合中
    for _ in range(n):
        ## 找到当前最短距离的那个没有加入到集合中的点
        t= -1
        for i in range(1, n+1):
            if st[i] == False and (t == -1 or dist[t] > dist[i]):
                t = i
        ## 将当前最短的点加入集合，并以此更新其他点的距离
        st[t] = True
        for j in range(1,n+1):
            dist[j] = min(dist[j], dist[t] + g[t][j])

dijkstra()
print(dist[n] if dist[n] != float("inf") else -1)