35284번 - 신촌 방수 계획

ICPC Sinchon의 캠퍼스는 $1,2,\dots,N$의 번호가 붙여진 $N$개의 건물과 서로 다른 두 건물 사이를 잇는 $M$개의 양방향 통로로 이루어져 있고, 모든 건물은 이 통로들을 통해 서로 연결되어 있다. 같은 건물을 연결하는 통로가 여러 개 있을 수 있다.

하지만 비 오는 날 통로를 지나면 비를 맞을 수밖에 없다. 이에 ICPC Sinchon은 건물에 우산 보관함을 설치하거나, 통로에 지붕을 설치하고자 한다. 지붕과 우산 보관함은 각각 아래와 같은 기능을 한다.

• 지붕을 설치한 통로는 비를 맞지 않고 이동할 수 있다.
• 우산 보관함이 있는 건물에 도달하면 우산을 빌릴 수 있다. 따라서 이후 어떤 통로를 지나더라도 비를 맞지 않고 이동할 수 있다. 빌린 우산을 다시 반납할 필요는 없다.

지붕과 우산 보관함을 모두 설치한 후에는 어떤 건물에서 출발해도 비를 맞지 않고 다른 모든 건물로 이동할 수 있어야 한다. 각 건물에 우산 보관함을 설치하는 비용과 각 통로에 지붕을 설치하는 비용이 주어질 때, 필요한 최소 비용을 구하여라.

첫 번째 줄에 건물의 수 $N$과 통로의 수 $M$이 공백으로 구분되어 주어진다. ($2\le N\le 100\, 000$; $N-1\le M\le 300\, 000$)

두 번째 줄에 $1,2,\dots,N$번 건물에 우산 보관함을 설치하기 위해 필요한 비용을 나타내는 $N$개의 정수 $c_1,c_2,\dots,c_N$이 공백으로 구분되어 주어진다. ($1\le c_i\le 10^{9}$)

세 번째 줄부터 $M$개의 줄에 걸쳐 각 통로에 대한 정보를 나타내는 세 개의 정수 $u$, $v$, $w$가 공백으로 구분되어 주어진다. 이는 $u$번 건물과 $v$번 건물을 잇는 통로가 존재하고, 이 통로에 지붕을 설치할 때 $w$의 비용이 듦을 의미한다. ($1\le w\le 10^{9}$)

첫 번째 줄에 필요한 최소 비용을 출력한다.