题目

QQ农场之勤劳的李放

背景

李放是一个勤劳的人，他从不在机房里偷懒，准点偷着每一个人的菜（-_-||）

但是机房里的人们并不是傻的，他们为了自己的菜不被李放偷光，每人在自己的农场里放了

一只战斗力为 5 的单身狗。李放因为害怕被单身狗的单身气息传染，他最多在每个人i的农场偷重量为ai的菜。

（呆的时间多了自己就会被单身气息传染）。并且大佬们为了捉住李放，在每个道路上铺满了图钉。

李放为了逃脱大佬们的追捕，在每条道路ei上他为了提高速度最多携带重量为wi的菜并且为了节省时间他只会携带从起点农场出发的菜。

李放也是个讲义气的人，他为了使贫穷的好兄弟们一起过上小康生活。于是他也叫来了woodheart，ACFox，heey,……等兄弟一起帮忙运菜和偷菜（假设李放有无数个兄弟）。

聪明的你能告诉李放和他兄弟们，他们一次最多能偷到多少菜运到菜市场（编号为n + 1）？

（假设李放从任意农场出发（兄弟们可以和他不同起点也可以相同））

输入格式

第一行 两个整数n，m。表示有n个农场，m条道路。

接下来一行 n 个数 a1，a2，……an表示最多在编号为i的农场偷重量为ai的菜。

接下来m行 每行三个数 x，y，wi。

表示从 x农场到 y农场有一条重量限制为wi的双向道路

输出格式

一行一个整数

表示李放和他兄弟们一次最多偷到多少菜运到菜市场（假设每个农场菜是无限的）

样例

input

2 3
11 6
1 2 7
2 3 8
1 3 6

output

14
提示
李放可以从一号农场偷重量为6的菜走第三条道路运到菜市场，

woodheart可以从一号农场偷重量为2的菜走第一条道路到二号农场，然后再走二号道路运到菜市场

ACfox可以从二号农场偷重量为6的菜走第二条路运到菜市场。

数据范围：

n,m均为非负数,ai,w<=1e9(1000000000)

(1) 30%的数据 n,m<=30;
(2) 60%的数据 n,m<=100;
(3) 100%的数据 n<=300,m<=800

因为出题人很懒不想做数据，所以建议使用 long long 型