2537: 桃子

Will 很喜欢吃桃子(Will 表示如果桃子不用剥皮就更好吃了,笑~)。某天 Will
来到了一片森林,森林中有 n 颗桃树,依次编号为 1, 2, ..., n。每棵树上有数量不等
的桃子。某些桃树之间有单向通行的小路,通过每条小路的时间也不一定相同。现在,
Will 提着一个最多可以容纳 k 个桃子的篮子,从编号为 1 的桃树出发,走过若干条小路
之后来到编号为 n 的桃树。当 Will 在路上走的时候,每走 1 分钟,他会从篮子中拿出
一个桃子来吃掉(如果篮子中还有桃子的话)。每到一棵桃树(包括起点和终点),他会
把这棵桃树上的所有桃子摘下来放入篮子中。
现在你的问题是:求 k 的最小值,使得 Will 能够不浪费任何桃子(每到一棵桃树,
这棵树上的所有桃子都能够被装入篮子中)。

第一行为两个整数 n 和 m,分别表示桃树的数量以及连接桃树的小路的数量。
接下来一行,n 个用一个空格隔开的整数,分别表示每一颗桃树上的果实的数量。
接下来 m 行,每行 3 个用空格隔开的整数 a, b, c,表示有一条小路能够从桃树 a
走到桃树 b,(注意小路一定是单向的),走过这条小路所需要的时间是 c 分钟。
从任意一棵桃树出发,Will 不可能沿着小路走若干条之后重新回到这棵桃树。(给
出的图是一个有向无环图。)
数据保证 Will 一定能够从桃树 1 走到桃树 n。

一行一个整数,表示 k 的最小值。

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

6