F. Сделай связным
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан неориентированный граф, состоящий из $$$n$$$ вершин. На каждой вершине записано число; число, записанное на вершине $$$i$$$, равно $$$a_i$$$. Изначально в графе нет ни одного ребра.

Вы можете добавлять ребра в граф за определенную стоимость. За добавление ребра между вершинами $$$x$$$ и $$$y$$$ надо заплатить $$$a_x + a_y$$$ монет. Также существует $$$m$$$ специальных предложений, каждое из которых характеризуется тремя числами $$$x$$$, $$$y$$$ и $$$w$$$, и означает, что можно добавить ребро между вершинами $$$x$$$ и $$$y$$$ за $$$w$$$ монет. Эти специальные предложения не обязательно использовать: если существует такая пара вершин $$$x$$$ и $$$y$$$, такая, что для нее существует специальное предложение, можно все равно добавить ребро между ними за $$$a_x + a_y$$$ монет.

Сколько монет минимально вам потребуется, чтобы сделать граф связным? Граф является связным, если от каждой вершины можно добраться до любой другой вершины, используя только ребра этого графа.

Входные данные

В первой строке заданы два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le m \le 2 \cdot 10^5$$$) — количество вершин в графе и специальных предложений, соответственно.

Во второй строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{12}$$$) — числа, записанные на вершинах.

Затем следуют $$$m$$$ строк, в каждой из которых заданы три целых числа $$$x$$$, $$$y$$$ и $$$w$$$ ($$$1 \le x, y \le n$$$, $$$1 \le w \le 10^{12}$$$, $$$x \ne y$$$), обозначающие спецпредложение: можно добавить ребро между вершинами $$$x$$$ и $$$y$$$ за $$$w$$$ монет.

Выходные данные

Выведите одно целое число — минимальное количество монет, которое необходимо потратить, чтобы сделать граф связным.

Примеры
Входные данные
3 2
1 3 3
2 3 5
2 1 1
Выходные данные
5
Входные данные
4 0
1 3 3 7
Выходные данные
16
Входные данные
5 4
1 2 3 4 5
1 2 8
1 3 10
1 4 7
1 5 15
Выходные данные
18
Примечание

В первом примере из условия можно соединить $$$1$$$ и $$$2$$$ при помощи $$$2$$$-го спецпредложения, а затем $$$1$$$ и $$$3$$$ без использования спецпредложения.

В следующих двух примерах оптимальный ответ можно получить без использования спецпредложений.