[백준 1504] 특정한 최단 경로

from queue import PriorityQueue
import sys

def Dijkstra(G,sp):
    
    INF=float("inf")
    dist=[INF]
    prev=[0]
    Q=set()
    que=PriorityQueue()

    for i in range(1,n+1):
        if i==sp:
            dist.append(0)
        else:
            dist.append(INF)
        prev.append(0)
        Q.add(i)
        que.put((dist[i],i))

    while Q!=set():
        while True:
            temp_u=que.get()[1]
            if temp_u in Q:
                u=temp_u
                break
        Q.remove(u)
        for i in range(1,len(G[u])+1):
            alt=dist[u]+G[u][i-1][1]
            if alt<dist[G[u][i-1][0]]:
                dist[G[u][i-1][0]]=alt
                prev[G[u][i-1][0]]=u
                que.put((alt,G[u][i-1][0]))
    
    return dist,prev

def Dijkstra_se(G,sp,ep):
    D,P=map(list, Dijkstra(G,sp))
    return D[ep]

n,m=map(int ,sys.stdin.readline().split())

G=[[] for _ in range(n+1)]
for i in range(1,m+1):
    u,v,w=map(int, sys.stdin.readline().split())
    G[u].append((v,w))
    G[v].append((u,w))
    
a,b=map(int, sys.stdin.readline().split())

m=Dijkstra_se(G,a,b)
ans=min(Dijkstra_se(G,1,a)+Dijkstra_se(G,b,n),Dijkstra_se(G,1,b)+Dijkstra_se(G,a,n))+m

if ans==float("inf"):
    print(-1)
else :
    print(ans)