{"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":"MD","content":"## 题目描述\n\n给定包含 $n$ 个结点的无向图。每个结点有点权 $a_i$。一开始图上没有边。\n\n在结点 $x$ 和结点 $y$ 之间加入一条边的代价为 $a_x+ a_y$。此外还有 $m$ 个特殊优惠 $(x, y, w)$,表示你可以花费代价 $w$ 在结点 $x$ 和结点 $y$ 之间加一条边。你不一定需要使用特殊优惠。\n\n请你求出使得图变成连通图的最小代价。\n\n## 输入格式\n\n第一行包含整数 $n, m$($1 \\le n \\le 2 \\cdot 10^5, 0 \\le m \\le 2 \\cdot 10^5$),表示图中结点数量和特殊优惠数量。\n\n第二行包含 $n$ 个整数 $a_1, a_2, \\dots, a_n$($1 \\le a_i \\le 10^{12}$),表示每个点权。\n\n接下来 $m$ 行,每行包含三个整数 $x, y, w$($1 \\le x, y \\le n, 1 \\le w \\le 10^{12}, x \\ne y$),表示特殊优惠。\n\n## 输出格式\n\n输出一个整数,表示使得图变成连通图的最小代价。\n\n\u003cp\u003eYou are given an undirected graph consisting of $$$n$$$ vertices. A number is written on each vertex; the number on vertex $$$i$$$ is $$$a_i$$$. Initially there are no edges in the graph.\u003c/p\u003e\n\u003cp\u003eYou may add some edges to this graph, but you have to pay for them. The cost of adding an edge between vertices $$$x$$$ and $$$y$$$ is $$$a_x + a_y$$$ coins. There are also $$$m$$$ special offers, each of them is denoted by three numbers $$$x$$$, $$$y$$$ and $$$w$$$, and means that you can add an edge connecting vertices $$$x$$$ and $$$y$$$ and pay $$$w$$$ coins for it. You don\u0027t have to use special offers: if there is a pair of vertices $$$x$$$ and $$$y$$$ that has a special offer associated with it, you still may connect these two vertices paying $$$a_x + a_y$$$ coins for it.\u003c/p\u003e\n\u003cp\u003eWhat is the minimum number of coins you have to spend to make the graph connected? Recall that a graph is connected if it\u0027s possible to get from any vertex to any other vertex using only the edges belonging to this graph.\u003c/p\u003e"}},{"title":"Input","value":{"format":"MD","content":"\u003cp\u003eThe first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \\le n \\le 2 \\cdot 10^5$$$, $$$0 \\le m \\le 2 \\cdot 10^5$$$) — the number of vertices in the graph and the number of special offers, respectively.\u003c/p\u003e\n\u003cp\u003eThe second line contains $$$n$$$ integers $$$a_1, a_2, \\dots, a_n$$$ ($$$1 \\le a_i \\le 10^{12}$$$) — the numbers written on the vertices.\u003c/p\u003e\n\u003cp\u003eThen $$$m$$$ lines follow, each containing three integers $$$x$$$, $$$y$$$ and $$$w$$$ ($$$1 \\le x, y \\le n$$$, $$$1 \\le w \\le 10^{12}$$$, $$$x \\ne y$$$) denoting a special offer: you may add an edge connecting vertex $$$x$$$ and vertex $$$y$$$, and this edge will cost $$$w$$$ coins.\u003c/p\u003e"}},{"title":"Output","value":{"format":"MD","content":"\u003cp\u003ePrint one integer — the minimum number of coins you have to pay to make the graph connected.\u003c/p\u003e"}},{"title":"Sample 1","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 2\n1 3 3\n2 3 5\n2 1 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Sample 2","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 0\n1 3 3 7\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e16\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Sample 3","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 4\n1 2 3 4 5\n1 2 8\n1 3 10\n1 4 7\n1 5 15\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e18\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"MD","content":"\u003cp\u003eIn the first example it is possible to connect $$$1$$$ to $$$2$$$ using special offer $$$2$$$, and then $$$1$$$ to $$$3$$$ without using any offers.\u003c/p\u003e\n\u003cp\u003eIn next two examples the optimal answer may be achieved without using special offers.\u003c/p\u003e"}}]}