간선 이어가기 2

정점 $n$개와 간선 $0$개로 이루어진 무방향 그래프가 있다. 여기에 가중치가 붙은 간선 $m$개가 적힌 간선 리스트가 주어진다. 리스트에 있는 간선을 원하는 순서로 하나씩 그래프에 추가하다가, 정점 $s$와 정점 $t$가 연결되는 순간 추가를 멈춘다. 두 정점이 간선을 따라 서로 오갈 수 있으면 연결된 것이다.

추가하는 순서를 마음대로 정할 수 있다. $s$와 $t$가 연결되는 순간까지 추가한 간선의 가중치 합이 가장 작아지도록 순서를 정하고, 그 최솟값을 구하시오.

첫째 줄에 정점의 개수 $n$과 간선 리스트의 간선 수 $m$이 주어진다. ($2 \le n \le 5000$, $1 \le m \le 100000$)

다음 $m$개의 줄에는 세 정수 $a$, $b$, $c$가 주어진다. 정점 $a$와 정점 $b$를 잇는 가중치 $c$인 간선이 리스트에 있다는 뜻이다. ($1 \le a, b \le n$, $1 \le c \le 100$, $a \ne b$)

마지막 줄에 두 정점 $s$와 $t$가 주어진다. ($1 \le s, t \le n$, $s \ne t$)

같은 두 정점을 잇는 간선이 리스트에 여러 개 있을 수 있다. 리스트의 간선을 모두 추가하면 그래프가 연결 그래프가 됨이 보장된다.

$s$와 $t$가 연결되는 순간까지 추가한 간선의 가중치 합의 최솟값을 첫째 줄에 출력한다.