창구 연결망

문제

은행 지점에는 1번부터 N번까지 번호가 붙은 N개의 창구가 있다. 모든 창구가 서로 연락할 수 있도록 창구 사이에 전용 회선을 설치하려 한다. 회선은 두 창구를 직접 잇는 선이며, 설치한 회선을 따라 다른 창구를 거쳐서 연락하는 것은 허용된다. 설치 방법은 두 가지다. 1. 일반 회선: 서로 다른 임의의 두 창구 i, j 사이에 설치할 수 있고, 비용은 a_i + a_j이다. 여기서 a_i는 i번 창구의 장비 등급 값이다. 2. 특약 회선: 입력으로 주어진 M개의 특약 중 하나를 고르면 해당하는 두 창구 사이에 정해진 비용 c로 설치할 수 있다. 같은 두 창구 쌍에 대한 특약이 여러 개일 수 있으며, 일반 회선과 특약 회선이 같은 쌍에 모두 가능할 수도 있다. 모든 창구가 회선을 통해 하나로 연결되도록 설치할 때 드는 총비용의 최솟값을 구하시오. 일반 회선은 어떤 쌍에도 설치할 수 있으므로 연결은 항상 가능하다. 총비용은 64비트 정수 범위 안에 들어간다.

입력

첫째 줄에 창구 수 N(2 ≤ N ≤ 200,000)과 특약 수 M(0 ≤ M ≤ 200,000)이 주어진다. 둘째 줄에 a_1, ..., a_N(1 ≤ a_i ≤ 1,000,000,000, 정수)이 주어진다. 이어 M개의 줄에 각각 특약의 두 창구 번호 u, v(1 ≤ u, v ≤ N, u ≠ v)와 비용 c(1 ≤ c ≤ 1,000,000,000, 정수)가 주어진다.

출력

모든 창구를 연결하는 데 필요한 최소 총비용을 한 줄에 출력한다.

4 1
5 2 7 4
3 4 3

16

2 0
1 1

2

3 2
10 10 10
1 2 5
2 3 5

10

출처: Devin.KR 자체 제작