Vào năm 20XX, công nghệ đã được phát triển vượt bậc. Con người khi di chuyển từ nơi này đến nơi khác sẽ không phải ngồi ở các phương tiện giao thông để di chuyển nữa, mà giờ, họ sẽ di chuyển thông qua các cổng dịch chuyển.

Ở một thành phố X, người ta đã xây dựng được ~n~ cổng dịch chuyển và chúng được kết nối với nhau để người dân đi lại thuận tiện nhất. Tuy nhiên, sau một sự cố ngoài mong muốn, hệ thống kết nối giữa các cổng dịch chuyển trong thành phố đã bị phá hủy hoàn toàn.

Vì thế, chính quyền thành phố cho sửa chữa lại các kết nối của thành phố. Biết rằng thành phố có ~n~ cổng dịch chuyển, mỗi cổng có một chi phí xây dựng là ~a_i~. Để kết nối hai cổng ~u~ và ~v~, họ cần một chi phí là ~a_u + a_v~.

Tuy nhiên có một số cổng đặc biệt được kết nối với nhau theo cách đặc biệt bằng ~m~ kết nối. Mỗi kết nối đó sẽ được cho dưới dạng ba số ~u, v~ và ~w~, tức là họ có thể kết nối từ cổng ~u~ đến cổng ~v~ với chi phí là ~w~. Hơn thế nữa, nếu như hai cổng ~u~ và ~v~ có thể nối bằng cách đặc biệt với chi phí là ~w~, họ vẫn có thể chọn cách nối thông thường với chi phí là ~a_u + a_v~.

Do dữ liệu quá lớn, bạn hãy viết chương trình giúp thành phố X tính xem chi phí nhỏ nhất để tất cả cổng kết nối với nhau là bao nhiêu? Biết rằng tất cả các cổng kết nối với nhau là ta có thể đi từ bất kỳ cổng nào đến bất kỳ cổng nào khác chỉ bằng cách sử dụng các kết nối đã được xây dựng.

Dữ liệu

Vào từ tệp văn bản CONT.INP:

• Dòng thứ nhất: gồm hai số nguyên dương ~n~ và ~m~ (~1 \le n \le 2 \cdot 10^5~, ~0 \le m \le 2 \cdot 10^5~) – lần lượt là số cổng của thành phố và số con đường đặc biệt;
• Dòng thứ hai: gồm ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 10^{12}~) – chi phí khi xây dựng các cổng;
• ~m~ dòng tiếp theo: mỗi dòng gồm ba số nguyên dương ~u, v~ và ~w~ (~1 \le u, v \le n~, ~1 \le w \le 10^{12}~, ~u \ne v~) – là các kết nối đặc biệt của thành phố X.

Kết quả

Đưa ra tệp văn bản CONT.OUT gồm một dòng duy nhất là một số nguyên không âm chứa kết quả của đề bài.

Ví dụ

Ví dụ 1

CONT.INP

3 2
1 3 3
2 3 5
2 1 1

CONT.OUT

5

Ví dụ 2

CONT.INP

4 0
1 3 3 7

CONT.OUT

16

Ví dụ 3

CONT.INP

5 4
1 2 3 4 5
1 2 8
1 3 10
1 4 7
1 5 15

CONT.OUT

18

Giải thích:

• Ở ví dụ thứ nhất, ta có thể kết nối hai cổng 1 và 2 bằng cách sử dụng kết nối đặc biệt thứ hai là ~(2, 1, 1)~, sau đó ta kết nối cổng 1 và 3 mà không sử dụng cách đặc biệt nào;
• Ở ví dụ thứ hai và thứ ba, ta có thể kết nối các cổng để được chi phí nhỏ nhất mà không cần sử dụng các kết nối đặc biệt.

Giới hạn

• Có 30% số test tương ứng với 30% số điểm có ~1 \le n \le 1000~, ~0 \le m \le 1000~;
• Có 20% số test khác tương ứng với 20% số điểm có ~1 \le n \le 2 \cdot 10^5~, ~m = 0~;
• Có 50% số test còn lại tương ứng với 50% số điểm có ~1 \le n \le 2 \cdot 10^5~, ~0 \le m \le 2 \cdot 10^5~.