일반적인 다익스트라
import sys
import heapq
INF = sys.maxsize
n, m = map(int, sys.stdin.readline().rstrip().split())
nodes = [[] for _ in range(n+1)]
for _ in range(m):
a, b, c = map(int, sys.stdin.readline().rstrip().split())
nodes[a].append([b, c])
nodes[b].append([a, c])
s, t = map(int, sys.stdin.readline().rstrip().split())
def Dijkstra():
distances = [INF for _ in range(n+1)]
distances[s] = 0
pq = []
heapq.heappush(pq, [0, s])
while pq:
cur_cost, cur_node = heapq.heappop(pq)
if distances[cur_node] < cur_cost: continue
for next_node, next_cost in nodes[cur_node]:
if distances[next_node] > next_cost + cur_cost:
distances[next_node] = next_cost + cur_cost
heapq.heappush(pq, [next_cost + cur_cost, next_node])
return distances[t]
print(Dijkstra())