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

因为找到他家的入口不是一件容易的事……

他们家很穷，但是他有个好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单位的钱。你需要求出找到入口最少需要花费多少单位的钱。

第1行包含两个正整数n、m，具体意义参考题目描述。

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

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

输出一行一个整数，表示找到入口花费的最少钱数。

【数据规模及约定】

存在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。