Escape Room

Wonbin went to an escape room cafe with his friends. The cafe has $N$ rooms numbered $1$ through $N$, and one friend is inside each room. Every room is completely isolated from the outside.

Wonbin felt bad for the friends who cannot get out, so he wants to install warps and emergency exits so that all of them can escape to the outside. He can install at most $M$ warps. Installing the $i$-th warp takes $c_i$ time, and once installed it lets a person move between room $a_i$ and room $b_i$. Each room can also have an emergency exit that connects directly to the outside, and installing an emergency exit in room $i$ takes $t_i$ time.

Unfortunately, Wonbin is not the brightest, so he cannot work on multiple installations of warps or emergency exits at the same time. In other words, he can start the next task only after the current one finishes.

Help Wonbin find the minimum time needed to install warps and emergency exits so that all of his friends can escape to the outside.

The first line gives the number of rooms $N$ and the number of warps that can be installed $M$. ($2 \le N \le 200\,000$, $1 \le M \le 100\,000$)

The next $M$ lines give three integers $a_i$, $b_i$, $c_i$ separated by spaces, describing a warp: installing a warp between room $a_i$ and room $b_i$ takes $c_i$ time. Multiple warps may connect the same pair of rooms. ($1 \le a_i, b_i \le N$, $1 \le c_i \le 10^4$, $a_i \ne b_i$)

The last line gives $N$ integers $t_1$, ..., $t_n$, where $t_i$ is the time needed to install an emergency exit in room $i$. ($1 \le t_i \le 10^4$)

Print the minimum time needed to install warps and emergency exits so that all of the friends can escape to the outside.