2243. 最小距离
1000ms
256MB
简单
最小生成树
题目描述
先有 $n$ 个点 $m$ 条边的无向图，要选 $n-1$ 条边连接 $n$ 个点。可以从任意一个点开始选边，连接下一个点，选中图中的 $1$ 个点，需要累加该点对应着数字。从 $a$ 点到达 $b$ 点，也需要累加边权值。
注意，构建完后，还要回到起点。求构建该树需要的最小数值是多少。
输入格式
第一行两个整数 $n$ 和 $m$，表示有 $n$ 个点，$m$ 条边。
连接的道路接下来行，每行一个整数，表示第 $i$ 个点对应的数字。
然后 $m$ 行，每行三个整数 $a, b, c$，表示 $a$ 到 $b$ 的边权值是 $c$。
输出格式
一个整数，为最小值。
样例 1
输入 (Input)
3 3 6 5 13 1 2 1 2 3 2 3 1 3
输出 (Output)
40
样例 2
输入 (Input)
5 7 6 5 13 8 18 4 1 7 5 2 5 1 5 16 2 3 20 3 1 18 4 3 12 2 4 15
输出 (Output)
154
全部数据 $5 \le n \le 10000$，$n-1 \le m \le 100000$，结果保证不超过 $maxlongint$。
{样例 1 解释：}
从 2 号点出发，到 1 号点，返回 2 号点，再到 3 号点，返回 2 号点。结束。
经过的值累加：$5 + 1 + 6 + 1 + 5 + 2 + 13 + 2 + 5 = 40$。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功