엘리니아 재건

메이플스토리의 엘리니아에는 거대한 나무의 줄기에 $N$ 개의 떠 있는 집과 각각 서로 다른 두 집을 양방향으로 연결하는 $M$ 개의 마법의 다리가 있다. 집은 $1$부터 $N$까지 번호가 붙어 있으며, 한 쌍의 집을 연결하는 마법의 다리는 최대 한 개이다.

최근 검은 마법사의 공격으로 일부 마법의 다리가 파괴되어, 모든 집이 연결된 상태가 아닐 수 있다는 소식이 전해졌다. 즉, 서로 다른 두 집을 한 개 이상의 마법의 다리를 통해 이동할 수 없는 경우가 생겼다는 것이다.

다행히도 마법사 연합에서 특별한 주문을 개발했다. 이 주문을 사용하면 어떤 집 $i$와 집 $j$를 연결하는 마법의 다리가 있을 때, 이 다리의 집 $j$ 쪽 끝을 떼어 다른 집 $k$로 옮길 수 있다. 그러면 마법의 다리는 집 $i$와 집 $k$를 연결하는 다리가 된다. 하지만, 이 주문을 사용할 때는 다리의 무게만큼의 마나가 소모되고, 집 $j$에서 다리를 떼어내는 데 추가 마나가 필요하다.

$N$ 개의 집에서 다리를 떼는 데 필요한 마나와, $M$ 개의 마법의 다리의 정보와 무게가 주어질 때, 모든 집이 연결된 상태가 되도록 하기 위해 필요한 최소 마나를 계산하는 프로그램을 작성하라.

입력 형식

첫 줄에 떠 있는 집의 개수를 나타내는 정수 $N$과 마법의 다리의 개수를 나타내는 정수 $M$이 공백으로 구분되어 주어진다. ($2 \le N \le 500\,000;$ $N-1 \le M \le 500\,000$)

그다음 줄에는 집에서 마법의 다리를 떼어내는 데 필요한 마나를 나타내는 $N$ 개의 정수 $C_1, C_2, \cdots, C_N$이 공백으로 구분되어 주어진다. 이는 집 $i$에서 마법의 다리를 떼어내는 데 필요한 마나 비용이 $C_i$임을 나타낸다. ($0 \le C_i \le 1\,000\,000\,000$)

이어지는 $M$ 개의 줄의 $i$ 번째 줄에는 $i$ 번째 마법의 다리의 정보를 나타내는 세 정수 $A_i$, $B_i$, $W_i$가 공백으로 구분되어 주어진다. 이는 $i$ 번째 마법의 다리가 집 $A_i$와 집 $B_i$를 연결하며, 무게가 $W_i$임을 나타낸다. ($1 \le A_i, B_i \le N;$ $A_i \neq B_i$; $0 \le W_i \le 1\,000\,000\,000$)

출력 형식

첫 줄에 모든 집이 연결된 상태가 되도록 하기 위해 필요한 최소 마나를 출력한다.

예제 1

5 4
1 0 2 6 2024
1 2 7
2 3 9
3 4 3
4 1 5

5

예제 2

3 3
0 0 0
1 2 1
2 3 1
3 1 1

0

예제 설명

입력 예제 1에서, 집 $5$에 연결된 마법의 다리가 없다. 집 $3$과 집 $4$를 연결하는 무게 $3$인 마법의 다리를 집 $3$에서 마나 $2$를 들여 떼어내어 집 $5$로 옮기면, 집 $5$와 집 $4$를 연결하는 마법의 다리로 바뀐다. 이때, 총 마나는 $3 + 2 = 5$이며, 이는 모든 집이 연결된 상태가 되도록 하는 최소 마나다.

입력 예제 2에서는 이미 모든 집이 마법의 다리로 연결된 상태이므로 다리를 옮길 필요가 없다. 따라서 추가적인 마나가 들지 않는다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설