测试数据来自 system/2195

时间限制：1秒　　内存限制：256M

---

【题目描述】

　　丛林中共有n 棵果树，每一棵果树上都有数量不等的果实。果树之间有单向边连接。你提着一个篮子从编号为1的果树出发，选择一条路径走到编号为n 的果树。每当你走到一棵果树的时候，你都会将这棵果树的所有果实采摘下来，放入篮子中，假设这个过程是不花费任何时间的。而当你在路上行走的时候，每走1分钟，你都会从篮子中拿出一个果实吃掉（如果篮子里还有果实的话）。

　　你的任务是求出你所携带的篮子至少要能够承担多少个果实的重量，才能够顺利地选择一条路径完成旅途，并且在途中不扔掉任何果实。（当到达第i棵果树时，还是要将这棵果树的全部果实放入篮子中）。

【输入格式】

　　第一行为两个整数n和m，分别表示果树的个数与单向边的条数。所有的果树从1到n 编号。　　
　　接下来一行， n个用空格隔开的整数，分别表示编号1..n 的果树上果实的个数。　　
　　接下来m ，每行三个用空格隔开的整数 x,y,c，表示从x 到y 有一条单向边相连，这条边通过所需的时间为c （分钟）。

【输出格式】

　　有且仅有一行，一个整数，表示篮子最少需要承担多少个果实的重量。

【输入输出样例】

　Input

4 4
5 7 6 4
1 2 3
1 3 3
2 4 100
3 4 1

　Output

9

【数据限制】

　　两颗不同树之间可能有多条边直接相连，但是没有一条边连接两颗相同的树。一定存在至少一条从树1到达树 的路径。每棵树上果实的数量，通过一条边所需的时间都是1~10000之间的整数。　
　　对于30%的数据，n≤10，m≤20 。　　
　　对于60%的数据，n≤100，m≤300。　　
　　对于100%的数据，n≤1000，m≤5000。

【来源】

　　Mr.he