题目描述

你去找某 bm 玩，到了门口才发现要打开他家的大门不是一件容易的事……

他家的大门外有 $n$ 个站台，用 $1$ 到 $n$ 的正整数编号。你需要对每个站台访问一定次数以后大门才能开启。站台之间有 $m$ 个单向的传送门，通过传送门到达另一个站台不需要花费任何代价。而如果不通过传送门，你就需要乘坐公共汽车，并花费 $1$ 单位的钱。值得庆幸的是，任意两个站台之间都有公共汽车直达。

现在给你每个站台必须访问的次数 $f_i$，对于站台 $i$，你必须恰好访问 $f_i$ 次（不能超过）。 我们用 $u,v,w$ 三个参数描述一个传送门，表示从站台 $u$ 到站台 $v$ 有一个最多可以使用 $w$ 次的传送门（不一定要使用 $w$ 次）。值得注意的是，对于任意一对传送门 $(u_1,v_1)$ 和 $(u_2,v_2)$，如果有 $u_1<u_2$，则有 $v_1\leq v_2$；如果有 $v_1<v_2$，则有 $u_1\leq u_2$；且 $u_1=u_2$ 和 $v_1=v_2$ 不同时成立。

你可以从任意的站台开始，从任意的站台结束。出发去开始的站台需要花费 $1$ 单位的钱。你需要求出打开大门最少需要花费多少单位的钱。

输入格式

第一行包含两个正整数 $n,m$，意义见题目描述。

第二行包含 $n$ 个正整数，第 $i$ 个数表示 $f_i$。接下来有 $m$ 行，每行有三个正整数 $u,v,w$，表示从 $u$ 到 $v$ 有一个可以使用 $w$ 次的传送门。

输出格式

输出一行一个整数，表示打开大门最少花费的钱数。

样例输入

4 3
5 5 5 5
1 2 1
3 2 1
3 4 1

样例输出

17

数据规模与约定

有 $20\%$ 的数据满足 $n\leq 10$，$m\leq 50$；对于所有的 $w,f_i$，满足 $1\leq w,f_i\leq 10$。

有 $50\%$ 的数据满足 $n\leq 1\times 10^3$，$m\leq 1\times 10^4$。

$100\%$ 的数据满足 $1\leq n\leq 1\times 10^4,1\leq m\leq 1\times 10^5$；对于所有的 $u,v$，满足 $1\leq u,v\leq n$，$u\neq v$；对于所有的 $w,f_i$，满足 $1\leq w,f_i\leq 5\times 10^4$。

以上的每类数据中都存在 $50\%$ 的数据满足对于所有的 $w,f_i$，有 $w=f_i=1$。