时间限制 1s

空间限制 256MB

【问题描述】

你去找路人甲玩，到了门口才发现一件有点小坑爹的事情

因为要开他家的大门不是一件容易的事（不能撬锁）……

他们家很穷，但是他有个好GF,所以他们家装饰的富丽堂皇。

他家的大门外有n个召唤师平台，用1到n的正整数编号。你需要对每个召唤师平台访问一定的次数以后大门才能开启。召唤师平台之间有m个单向的飞行阵，通过飞行阵到达另一个召唤师平台不需要花费任何代价。而如果不通过飞行阵，你就需要乘坐飞艇，并花费1单位的钱。值得庆幸的是，我能做飞艇到那里，就可以从那里坐回来。

现在给你每个召唤师平台必须访问的次数Fi，对于召唤师平台i，你必须恰好访问Fi次（不能超过）。

我们用a、b、c三个参数描述一个飞行阵，表示从召唤师平台a到召唤师平台b有一个最多可以使用c次的飞行阵（不一定非要使用c次）。值得注意的是，对于任意一对飞行阵(a1,b1)和(a2,b2)，如果有a1<a2，则有b1≤b2；如果有b1<b2，则有a1≤a2；且a1=a2和b1=b2不同时成立。

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

【输入格式】

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

第二行包含n个正整数，第i个数表示Fi。

接下来有m行，每行有三个正整数a、b、c，表示从a到b有一个可以使用c次的飞行阵。

【输出格式】

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

【样例输入】

4 3

5 5 5 5

1 2 1

3 2 1

3 4 1

【样例输出】

17

【数据规模及约定】

有20%的数据满足n≤10，m≤50；对于所有的c、Fi，满足1≤c,Fi≤10。有50%的数据满足n≤1000，m≤10000。100%的数据满足1≤n≤10000，1≤m≤100000；对于所有的a、b，满足1≤a,b≤n，a≠b；对于所有的c、Fi，满足1≤c,Fi≤50000。

以上的每类数据中都存在50%的数据满足对于所有的c、Fi，有c=Fi=1。