N = 510
inf = float('inf') # py中的表示最小值
g = [[inf]*N for i in range(N)]
dist = [inf] * N
state = [False] * N


def dijkstra():
    dist[1] = 0

    # 所有还没有确定的点中找到dist最短的点
    for i in range(1,n+1):
        t = -1 # 用来标记还没有使用的 点 的最小值的点的位置
        for j in range(1,n+1):
            if(not state[j] and (t == -1 or dist[t] > dist[j])):
                # j 表示还灭有确定的最短路点
                t = j
        state[t] = True
        # 用t节点，当前的dis可以认为是最短路了
        for j in range(1,n+1):
            dist[j] = min(dist[j],dist[t]+g[t][j])
    if dist[n] == inf: # 表示1号到n号节点不连通
        return -1
    else:
        return dist[n]


if __name__ == "__main__":
    n,m = map(int,input().split())
    while m > 0:
        a,b,c = map(int,input().split())
        g[a][b] = min(g[a][b],c)
        m -= 1
    t = dijkstra();
    print(t)