{"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":"赵老师因为感冒回家进行休息\u003cbr\u003e\n在睡梦中他竟然来到了一个神奇的地方\u003cbr\u003e\n这个地方可以抽象为n个点,每个点有一个点权,第i个点的点权为a_i\u003cbr\u003e\n此时,他的脑海里竟然浮现出了一段文字:\u003cbr\u003e\n卑鄙的异乡人啊,\u003cbr\u003e\n你太年轻太简单了,有时还很朴素\u003cbr\u003e\n我需要给你一些微小的考验\u003cbr\u003e\n所有点联通之时,\u003cbr\u003e\n返程之路将浮现。\u003cbr\u003e\n\u003cbr\u003e\n赵老师知道,想要在点i和点j之间连一条边,所需时间为a_i+a_j\u003cbr\u003e\n但是作为一个单身多年的魔法师,他可以施展m次魔法,第i次魔法可以在x_i和y_i之间连一条边,所需时间是w_i\u003cbr\u003e\n赵老师清楚的记得,第二天他还需要上课,因此你需要帮他算出将所有点联通所需的最短时间是多少"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e第一行有两个正整数n,m (1≤ n 2·10^5,0≤m ≤3· 10^5) \u003c/p\u003e\n\u003cp\u003e第二行有n个正整数 :a_1, a_2, ..., a_n(1≤ a_i≤ 10^{12}).\u003c/p\u003e\n\u003cp\u003e之后m行,每行有三个正整数:x,y,w (1≤ x, y ≤n,1 ≤ w≤ 10^{12},x≠ y) .\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e输出一个正整数,将所有点联通所需的最短时间.\u003c/p\u003e"}},{"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":"\u003cp\u003e第一个样例中,将1和2连接,需要花费1单位时间,之后将1和3连接,花费4单位时间.\u003c/p\u003e"}}]}