#緑以下Ex-A import heapq as hq N,M = map(int,input().split()) #G[i][x]: xは0なら行き、1なら帰り G = [[[] for _ in range(2)] for _ in range(N)] for _ in range(M): u,v,t = map(lambda x:int(x)-1,input().split()); t+=1 G[u][0].append((v,t)); G[v][1].append((u,t)) #dist_1[k]: 町N-2→町k, 町k→町N-2 dist_1 = [[10**18]*2 for _ in range(N)] Q = [(0,N-2,0),(0,N-2,1)] while Q: time,now,x = hq.heappop(Q) if dist_1[now][x] < time: continue dist_1[now][x] = time for next,cost in G[now][x]: if dist_1[next][x] > time + cost: hq.heappush(Q,(time+cost, next, x)) #dist_2[k]: 町N-1→町k, 町k→町N-1 dist_2 = [[10**18]*2 for _ in range(N)] Q = [(0,N-1,0),(0,N-1,1)] while Q: time,now,x = hq.heappop(Q) if dist_2[now][x] < time: continue dist_2[now][x] = time for next,cost in G[now][x]: if dist_2[next][x] > time + cost: hq.heappush(Q,(time+cost, next, x)) #順に答えを出力 for k in range(N-2): ans = 10**18 ans = min(ans, dist_1[k][1] + dist_1[N-1][0] + dist_2[k][0]) ans = min(ans, dist_2[k][1] + dist_2[N-2][0] + dist_1[k][0]) print(ans if ans < 10**18 else -1)