时间限制：1秒　　内存限制：256M

---

【问题描述】

　　有 \(N\) 个学生，编号依次为 1 到 \(N\)。有 \(M\) 条道路连接这些学生的家，每条道路都是双向的。第 \(k\) 条道路连接的是学生 \(U_k\) 和 \(V_k\) 的家，通行需要 \(T_k\) 的时间。两学生家之间最多只有一条道路。

　　H老师打算到 \(N\) 个学生中家访，但他选择道路时，希望保持各家连通的情况下去掉尽量多的道路。他选择从任意一个学生家出发开始家访。当他走访完所有的学生之后，还要回到他的出发地。每次路过学生 \(i\) 的家时，他必须花 \(C_i\) 的时间和该学生交谈（即使之前已经家访过，也要留下来再谈一次）。 注意H老师在出发和回去的时候，都要和出发地的学生谈一次话。

　　请你计算一下，H老师要选择哪些道路，才能让家访的时间变得最少？

【输入格式】

　　第一行包含两个用空格分开的整数：\(N\) 和 \(M\)。
　　第二行到 \(N + 1\) 行：第 \(i + 1\) 行包括一个整数 \(C_i\)。
　　第 \(N + 2\) 行到 \(N + M + 1\) 行：第 \(N + k + 1\) 行包括三个用空格分开的整数 \(U_k，E_k\) 和 \(L_k(1 ≤ U_k, V_k ≤ N, Uk ≠ Vk)\)。

【输出格式】

　　一个整数，表示忽悠所有奶牛需要的最少时间。

【输入输出样例】

　Input

5 7
10
10
20
6
30
1 2 5
2 3 5
2 4 12
3 4 17
2 5 15
3 5 6
4 5 12

　Output

176

【数据说明】

　　对于 \(100\%\) 的数据 \(5 ≤ N ≤ 10,000\)，\(N − 1 ≤ P ≤ 100,000\)，\(1 ≤ C_i,L_k ≤ 1,000\)。

【来源】

　　Mr.he