test

'''
邻接矩阵
'''
n,m = map(int,input().split());
INF = float('inf');

g = [[INF] * (n + 1) for _ in range(n +1)];
dist = [INF] * (n + 1);
st = [0] * (n + 1);

def dijkstra():
    global n,INF;
    
    dist[1] = 0;
    for _ in range(n): #n次迭代确定n个最短路
        #从未标记的点中找一个最短的节点(步骤2)
        x = -1;
        for j in range(1,n + 1): 
            if st[j] == 0 and (x == -1 or dist[x] > dist[j]):x = j;
        #利用x来更新其他边 利用更新更新最短路(步骤3) 
        for y in range(1,n + 1): 
            dist[y] = min(dist[y],dist[x] + g[x][y]);
            
        st[x] = 1;
    if dist[n] == INF:return -1;
    else:return dist[n];
    
    
def main():
    for _ in range(m):
        x,y,w = map(int,input().split());
        g[x][y] = min(g[x][y],w);
    
    print(dijkstra());
main();