### 问题背景 唐三成神，在嘉陵关大战胜利后，他准备摧毁斗罗大陆上所有的武魂殿。 ### 问题描述 已知，在斗罗大陆上，一共有 $n$ 座武魂殿，所有武魂殿之间共有 $m$ 条有向边，构成了一张有向无环图。 对于编号为 $i$ 的武魂殿，摧毁它需要消耗的兵力为 $a_i$ 。唐三的天斗军队每次只能按照边的方向来行军，只有每座武魂殿被摧毁后，唐三军队才能继续前进。在通过边权为 $w$ 的边时，由于武魂殿的伏击，唐三军队会额外损失掉 $w$ 个兵力。 如果一座武魂殿，可以从多座武魂殿通过有向边到达，为了减小兵力的消耗，唐三的军队会选择其中的一条边通过。 在这张有向无环图中，有一些武魂殿的出度为 $0$ ，这些点被称为武魂圣殿。 唐三想知道，摧毁所有武魂圣殿最少需要多少兵力？ ### 输入格式 第一行输入两个正整数 $n$ 和 $m$ ，表示图的点数和边数。 第二行输入 $n$ 个正整数，其中第 $i$ 个数表示 $a_i$ 。 接下来共有 $m$ 行，每一行输入三个正整数 $u,v,w$ ，表示从 $u$ 到 $v$ 有一条有向边，边权为 $w$ 。 ### 输出格式 输出摧毁所有武魂圣殿最少需要的兵力。如果有多座武魂圣殿，按编号从小到大输出，每输出一个换一行。 ### 样例输入 ```cpp 9 10 11 13 21 30 40 33 27 43 20 1 4 17 2 4 23 2 5 19 3 5 29 4 6 31 5 6 13 5 7 7 6 8 41 7 8 47 7 9 3 ``` ### 样例输出 ```cpp 196 129 ``` ### 数据规模 对于所有数据，$1 \leq n \leq 10^5$ ，$1 \leq m \leq 2 ×10^5$ ，$1 \leq a_i \leq 10^4$ ，$1 \leq u,v \leq n$ ，$1 \leq w \leq 10^4$ 。