23743번 - 방탈출

문제

원빈이는 친구들과 함께 방탈출 카페에 갔다. 방탈출 카페에는 1ドル$번부터 $N$번까지 총 $N$개의 방이 있고, 각 방에는 친구들이 한 명씩 들어가 있다. 모든 방은 외부로부터 완전히 독립되어 있다.

방에서 탈출하지 못하는 친구들이 답답했던 원빈이는 모든 친구들이 출구로 탈출할 수 있도록 워프와 비상탈출구를 설치하려고 한다. 워프는 최대 $M$개까지 설치할 수 있는데, $i$번째 워프는 설치하는 데 $c_i$의 시간이 걸리고, 워프를 설치하면 $a_i$번 방과 $b_i$번 방 사이를 이동할 수 있다. 또한 각 방에는 출구로 바로 연결되는 비상탈출구를 설치할 수 있는데, $i$번 방에 비상탈출구를 설치하는 데 걸리는 시간은 $t_i$이다.

안타깝게도 원빈이는 머리가 나빠 워프나 비상탈출구의 설치 작업을 동시에 여럿 진행할 수 없다. 즉 한 작업이 끝나고 나서야 다음 작업을 이어서 시작할 수 있다.

원빈이를 도와 모든 친구들이 출구로 탈출할 수 있도록 워프와 비상탈출구를 설치하는 데 걸리는 최소 시간을 구해보자.

입력

첫 번째 줄에는 방의 개수 $N$과 설치할 수 있는 워프의 개수 $M$이 주어진다. (2ドル \le N \le 200,000円,ドル 1ドル \le M \le 100,000円$)

다음 $M$개의 줄에는 워프의 정보를 나타내는 세 정수 $a_i,ドル $b_i,ドル $c_i$가 공백으로 구분되어 주어지는데, 이는 $a_i$번 방과 $b_i$번 방 사이를 잇는 워프를 설치하는 데 걸리는 시간이 $c_i$라는 의미이다. 같은 두 개의 방을 잇는 워프가 여러 개 존재할 수 있다. (1ドル \le a_i, b_i \le N,ドル 1ドル \le c_i \le 10^4,ドル $a_i \ne b_i$)

마지막 줄에는 $N$개의 정수 $t_1,ドル ..., $t_n$이 주어지는데, $t_i$는 $i$번째 방에 비상탈출구를 설치하는 데 드는 시간을 의미한다. (1ドル \le t_i \le 10^4$)

출력

모든 친구들이 출구로 탈출할 수 있도록 워프와 비상탈출구를 설치하는 데 걸리는 최소 시간을 출력한다.

제한

힌트