盛夏的果实

admin

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

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

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

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

【输入样例】

4 4
5 7 6 4
1 2 3
1 3 3
2 4 100
3 4 1
1
2
3
4
5
6
【输出样例】

9
1
【数据范围】
两颗不同树之间可能有多条边直接相连，但是没有一条边连接两颗相同的树。一定存在至少一条从树1到达树 的路径。每棵树上果实的数量，通过一条边所需的时间都是1~10000之间的整数。

对于30%的数据，n<=10，m<=20
对于60%的数据，n<=100，m<=300
对于100%的数据，n<=1000，m<=5000