题目描述

W 市爆发了严重的肺炎疫情。为了应对疫情，W 市需要对下属每一个社区进行巡回调查。

W市共有 $n$ 个街区，街区之间由 $m$ 条不相同的有向道路相连，没有任何一条道路是自己通向自己的，并且是保证弱联通的。通过每条道路需要消耗一定的燃油费用。

现在你需要派出一些工作人员来寻访每个街区。对于每个工作人员，你需要给他分派一些街区，之后工作人员会按照给定的顺序在这些街区反复循环，每周循环一次。请注意，工作人员只会检查你给他分配的街区，在分配的街区之间经过的街区，工作人员并不会下车。同时为了防止人员浪费，任何一个街区只能接受一位工作人员的检查。当然，如果必要，他也会经过重复的街区。

工作人员的花费是这样的：若是某个工作人员只分配到了一个街区 $u$，那么他需要每周消耗 $a_u$ 的停留费用。若是被分配到了多于一个的街区，那么他的花费就是环绕这些点一圈最后回到起点的道路燃油费用之和。

现在你需要知道，在工作人员数量无限的情况下，每周最少需要多少费用可以将整个 W 市完全巡查。

输入格式

第一行两个整数 $n,m$，意义如题。

第二行 $n$ 个整数，为数组 $a$。

接下来 $m$ 行，每行三个整数 $u_i,v_i,w_i$ 表示存在一条连接 $u_i,v_i$ 的有向边，通行时付出的代价为 $w_i$。

输出格式

一个整数，表示答案。

3 3
30 25 30
1 2 3
2 3 5
3 1 10

18

提示

对于所有的数据 $1\leq n\leq 500,1\leq m\leq \min\{5000,n\times(n-1)\},0\leq a_i,w_i\leq 10^9$，保证图弱连通，无自环、无重边。

对于不同的测试点，我们有如下约束：