Вам дан неориентированный граф, состоящий из \(n\) вершин. На каждой вершине записано число; число, записанное на вершине \(i\), равно \(a_i\). Изначально в графе нет ни одного ребра.
Вы можете добавлять ребра в граф за определенную стоимость. За добавление ребра между вершинами \(x\) и \(y\) надо заплатить \(a_x + a_y\) монет. Также существует \(m\) специальных предложений, каждое из которых характеризуется тремя числами \(x\), \(y\) и \(w\), и означает, что можно добавить ребро между вершинами \(x\) и \(y\) за \(w\) монет. Эти специальные предложения не обязательно использовать: если существует такая пара вершин \(x\) и \(y\), такая, что для нее существует специальное предложение, можно все равно добавить ребро между ними за \(a_x + a_y\) монет.
Сколько монет минимально вам потребуется, чтобы сделать граф связным? Граф является связным, если от каждой вершины можно добраться до любой другой вершины, используя только ребра этого графа.
Выходные данные
Выведите одно целое число — минимальное количество монет, которое необходимо потратить, чтобы сделать граф связным.
Примечание
В первом примере из условия можно соединить \(1\) и \(2\) при помощи \(2\)-го спецпредложения, а затем \(1\) и \(3\) без использования спецпредложения.
В следующих двух примерах оптимальный ответ можно получить без использования спецпредложений.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
1 3 3
2 3 5
2 1 1
|
5
|
|
2
|
4 0
1 3 3 7
|
16
|
|
3
|
5 4
1 2 3 4 5
1 2 8
1 3 10
1 4 7
1 5 15
|
18
|