{"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":"You are given a graph with vertices, each having a cost associated with it. Your task is to make the graph connected by adding edges between vertices, with the option to utilize special offers. Each edge incurs a cost equal to the sum of the costs of the vertices it connects. However, there are special offers available where you can add an edge between certain vertices at a discounted cost. What is the minimum total cost required to make the graph connected?"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains two integers n and m ( 1 \u003c\u003d n \u003c\u003d 2 * 10^5 , 0 \u003c\u003d m \u003c\u003d 2 * 10^5 ) representing the number of vertices in the graph and the number of available special offers, respectively.\u003cbr\u003e\n\nThe second line contains n integers a_1, a_2, ... , a_n ( 1 \u003c\u003d a_i \u003c\u003d 10^{12} ) representing the costs associated with each vertex.\u003cbr\u003e\n\nThe following m lines each contain three integers x , y , and w ( 1 \u003c\u003d x, y \u003c\u003d n , 1 \u003c\u003d w \u003c\u003d 10^{12} , x !\u003d y ) denoting a special offer: adding an edge between vertex x and vertex y with a discounted cost of w coins.\n"}},{"title":"Output","value":{"format":"HTML","content":"Print one integer representing the minimum total cost required to make the graph connected."}},{"title":"Example","value":{"format":"HTML","content":"3 2 \u003cbr\u003e\n1 3 3\u003cbr\u003e\n2 3 5\u003cbr\u003e\n2 1 1\u003cbr\u003e\n"}},{"title":"Ans","value":{"format":"HTML","content":"5"}}]}