2242: 盛夏的果实
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：4
解决：0
题目描述
丛林中共有棵果树，每一棵果树上都有数量不等的果实。果树之间有单向边连接，而且从任何一棵果树开始不可能通过若干单向边走回自身。你提着一个篮子从编号为1的果树出发，选择一条路径走到编号为的果树。每当你走到一棵果树的时候，你都会将这棵果树的所有果实采摘下来，放入篮子中，假设这个过程是不花费任何时间的。而当你在路上行走的时候，每走1分钟，你都会从篮子中拿出一个果实吃掉（如果篮子里还有果实的话）。
你的任务是求出你所携带的篮子至少要能够承担多少个果实的重量，才能够顺利地选择一条路径完成旅途，并且在途中不扔掉任何果实。（当到达第棵果树时，还是要将这棵果树的全部果实放入篮子中）。
输入
输入文件第一行为两个整数n,m，分别表示果树的个数与单向边的条数。所有的果树从1到n编号。
接下来一行，n个用空格隔开的整数，分别表示编号1~n
接下来m行，每行三个用空格隔开的整数a,b,c，表示从a到b有一条单向边相连，这条边通过所需的时间为c（分钟）。
输出
输出文件有且仅有一行，一个整数，表示篮子最少需要承担多少个果实的重量。
样例输入 复制
4 4
5 7 6 4
1 2 3
1 3 3
2 4 100
3 4 1
样例输出 复制
9提示
限制条件：
l 1<=n<=1000,1<=m<=5000。
l 两颗不同树之间可能有多条边直接相连，但是没有一条边连接两颗相同的树。
l 一定存在至少一条从树1到达树n的路径。
l 每棵树上果实的数量，通过一条边所需的时间都是1~10000之间的整数。
l 对于30%的数据，n<=10,m<=20。
l 对于60%的数据，n<=100,m<=300。