Problem
今天，埃纳城堡正在举办一个馅饼节，有 n 家面包店参加，每家面包店都有自己唯一的编号，从 1 到 n。
一些面包店由双向道路连接，但如果可以从面包店 i 步行到面包店 j，那么它们之间只有一条路。
当 En 在第 i 家面包店吃馅饼时，他得到了 A
i 种乐趣。如果它经过一些面包店 v 和 u 之间的道路，那么馅饼的美味香气会带给 C
v,u 乐趣。
恩不想去每家面包店不止一次（有些可能根本不去），但她想充分利用这个节日。
他将从其中一家面包店开始，并且只会使用现有道路在它们之间穿行。
帮助恩确定他可以获得的最大可能的快乐。
输入：
第一行包含数字 n (1 <= n <= 50000) - 面包店的数量，以及数字 k - 面包店之间现有道路的数量。
第二行包含 n 个数字 A
i (0 <= A
i <= 10000) - 第 i 家面包店的馅饼的乐趣。
然后是k行，每行包含3个数字v, u, C (1 <= v, u <= n; v ≠ u; 0 <= C <= 10000)，意思是中间有一条路面包店编号为v和u，这条路上的香气带来了C的愉悦。
输出：
打印一个数字——最大可能的满意度。
示例：
<正文>
| 输入 |
输出 |
2 1
1 1
1 2 1
| 3 |
8 7
1 5 4 6 10 1 2 2
1 2 1
2 3 10
2 4 1
4 5 1
4 6 2
6 7 2
6 8 3
| 37 |
说明：
在第一个示例中，您需要从第一个面包店（1 个点心）开始，沿着第一个和第二个面包店之间的路走（1 个点心），然后参观第二个面包店（1 个点心）。总的快乐 - 1+1+1 = 3。
在第二个示例中，您需要从第 5 家面包店（10 种乐趣）开始，沿着第 5 家面包店和第 4 家面包店之间的路走（1 种乐趣），参观第 4 家面包店（6 种乐趣），沿着第 4 家和第 2 家之间的路走面包店（1 款），参观第二家面包店（5 款），沿着第二和第三家面包店之间的路走（10 款），参观第三家面包店（4 款）。总快乐度 - 10+1+6+1+5+10+4 = 37。