Connecting Edges 2

An undirected graph starts with $n$ vertices and $0$ edges. You are given an edge list of $m$ weighted edges. You add the edges of the list to the graph one at a time, in any order you like, and you stop the moment vertex $s$ and vertex $t$ become connected. Two vertices are connected when you can travel from one to the other along edges.

Choose the order that makes the total weight of the added edges as small as possible at the moment $s$ and $t$ become connected, and report that minimum.

The first line contains the number of vertices $n$ and the number of edges in the list $m$. ($2 \le n \le 5000$, $1 \le m \le 100000$)

Each of the next $m$ lines contains three integers $a$, $b$, $c$, meaning the list holds an edge of weight $c$ between vertex $a$ and vertex $b$. ($1 \le a, b \le n$, $1 \le c \le 100$, $a \ne b$)

The last line contains the two vertices $s$ and $t$. ($1 \le s, t \le n$, $s \ne t$)

The list may hold several edges between the same pair of vertices. Adding every edge of the list is guaranteed to make the graph connected.

Print on the first line the minimum total weight of the edges added up to the moment $s$ and $t$ become connected.