{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"Вам дан неориентированный граф, состоящий из n вершин. На каждой вершине записано число; число, записанное на вершине i, равно a[i]. Изначально в графе нет ни одного ребра.\n\u003cp\u003e\u003c/p\u003e\nВы можете добавлять ребра в граф за определенную стоимость. За добавление ребра между вершинами x и y надо заплатить a[x]+a[y] монет. Также существует m специальных предложений, каждое из которых характеризуется тремя числами x, y и w, и означает, что можно добавить ребро между вершинами x и y за w монет. Эти специальные предложения не обязательно использовать: если существует такая пара вершин x и y, такая, что для нее существует специальное предложение, можно все равно добавить ребро между ними за a[x]+a[y] монет.\n\u003cp\u003e\u003c/p\u003e\nСколько монет минимально вам потребуется, чтобы сделать граф связным? Граф является связным, если от каждой вершины можно добраться до любой другой вершины, используя только ребра этого графа."}},{"title":"Input","value":{"format":"HTML","content":"В первой строке заданы два целых числа n и m (1≤n≤2⋅10^5, 0≤m≤2⋅10^5) — количество вершин в графе и специальных предложений, соответственно.\n\u003cp\u003e\u003c/p\u003e\nВо второй строке заданы n целых чисел a[1],a[2],…,a[n] (1≤a[i]≤10^12) — числа, записанные на вершинах.\n\u003cp\u003e\u003c/p\u003e\nЗатем следуют m строк, в каждой из которых заданы три целых числа x, y и w (1≤x,y≤n, 1≤w≤10^12, x≠y), обозначающие спецпредложение: можно добавить ребро между вершинами x и y за w монет."}},{"title":"Output","value":{"format":"HTML","content":"Выведите одно целое число — минимальное количество монет, которое необходимо потратить, чтобы сделать граф связным."}},{"title":"Examples","value":{"format":"HTML","content":"\u003cdiv class\u003d\"sample-test\"\u003e \n \u003cdiv class\u003d\"input\"\u003e \n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e \n \u003cpre\u003e3 2\n1 3 3\n2 3 5\n2 1 1\n\u003c/pre\u003e\n \u003c/div\u003e \n \u003cdiv class\u003d\"output\"\u003e \n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e \n \u003cpre\u003e5\n\u003c/pre\u003e\n \u003c/div\u003e \n \u003cdiv class\u003d\"input\"\u003e \n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e \n \u003cpre\u003e4 0\n1 3 3 7\n\u003c/pre\u003e\n \u003c/div\u003e \n \u003cdiv class\u003d\"output\"\u003e \n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e \n \u003cpre\u003e16\n\u003c/pre\u003e\n \u003c/div\u003e \n \u003cdiv class\u003d\"input\"\u003e \n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e \n \u003cpre\u003e5 4\n1 2 3 4 5\n1 2 8\n1 3 10\n1 4 7\n1 5 15\n\u003c/pre\u003e\n \u003c/div\u003e \n \u003cdiv class\u003d\"output\"\u003e \n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e \n \u003cpre\u003e18\n\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}},{"title":"Note","value":{"format":"HTML","content":"В первом примере из условия можно соединить 1 и 2 при помощи 2-го спецпредложения, а затем 1 и 3 без использования спецпредложения.\n\u003cp\u003e\u003c/p\u003e\nВ следующих двух примерах оптимальный ответ можно получить без использования спецпредложений."}}]}