{"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":"\u003cp\u003e不知不觉得暑假已经结束了,身为21级的小A很快就迎来了一场选拔赛。但由于小A在暑假里沉迷于提瓦特大陆,早就将自己所学过的知识点忘得一干二净。不得已只能放下手机开始复习。\u003c/p\u003e\n\u003cp\u003e一共有 n 个知识点,编号为 $i$ 知识点的难度为正整数 $a_i$ 。小A的复习方式很特殊,他喜欢通过在知识点之间建立“联系”进行复习,若编号为 i 的知识点和编号为 j 的知识点建立了“联系”,那么小A可以通过知识点 i 联想到 j,当然也可以从 j 联想到 i ,建立该“联系”所要花费的时间为$a_i+a_j$。另外小A在之前学习的时候记了 m 条笔记,每条笔记包含三个正整数 x, y, w,他可以借助笔记将编号为 x 和 y 的知识点建立“联系”,花费时间为w。当然小A也可以选择无视该条笔记,即不借助笔记建立“练习”。如果小A可以从任意一个知识点出发联想到其他任意的知识点,那么视为小A复习完了所有知识点。\u003c/p\u003e\n\u003cp\u003e由于原神对小A的诱惑力实在是太大了,他想尽快复习完所有的知识点,重返提瓦特大陆。请你帮助他计算出复习完所有知识点所需要的最短时间。\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e第一行包含两个整数n和m($1≤n≤2⋅10^5$,$0≤m≤2⋅10^5$)--分别是知识点的数量和笔记的条数。\n\u003c/p\u003e\n\u003cp\u003e第二行包含n个整数$a_1,a_2,...,a_n(1≤a_i≤10^{12})$--编号为 i 的知识点的难度。\u003c/p\u003e\n\u003cp\u003e然后是m行,每行包含三个整数x,y和w$(1≤x,y≤n,1≤w≤10^{12},x≠y)$表示一条笔记:小A可以选择借助该条笔记建立“联系”,花费时间为w。\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e输出一个整数,表示最少时间\u003c/p\u003e"}},{"title":"Sample 1","value":{"format":"HTML","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"}}]}