学习计划

题目描述

小明很喜欢学习，他经常找同学借学习资料。

某天小明心血来潮，制定了一个学习计划，计划上写着$n$位同学的名字，依次编号为$1$,$2$,$\ldots$,$n$。每位同学有数量不等的资料。由于这天是周末，小明必须去这些同学的家里。某些同学的家之间有单向通行的小路，通过每条小路的时间也不一定相同。现在，小明背着一个最多可以放$k$份学习资料的书包，他决定先拜访编号为$1$的同学，走过若干条小路之后，来到编号为$n$的同学的家。为了节省时间，他决定走到编号为$n$的同学的家后，就不再拜访其他同学，而是直接回家。当小明在路上走的时候，每走$1$单位时间，他就会看完一份学习资料（如果还有学习资料）。每到一位同学的家（包括$1$和$n$），他会将这位同学所有的学习资料放进他的背包，直到放满。

现在你的问题是：求$k$的最小值，使得小明能够不浪费任何一份学习材料，即每到一位同学的家，他能把这个同学的所有学习资料放进背包。

题目保证小路构成一个有向无环图。

输入格式

第一行两个整数$n$，$m$，表示计划上的同学个数和小路个数。

第二行$n$个整数，分别表示每位同学的学习资料份数（小于等于$10000$）。

第三行到第$m+2$行，每行三个整数$a$，$b$，$c$，表示小路的两个端点以及消耗的时间。

输出格式

一行一个整数，表示$k_{min}$。

数据范围与提示

• 对于$30\%$的数据，$3 \leq n \leq 10$，$3 \leq m \leq 20$；
• 对于$60\%$的数据，$3 \leq n \leq 1000$，$3 \leq m \leq 10000$；
• 对于$100\%$的数据，$3 \leq n \leq 10000$，$3 \leq m \leq 30000$，$1 \leq a,b,c \leq 10000$。

样例

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

6