You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

####题目描述 中考之后，wlc开始了自己的旅行计划。在旅行过程中，有 $n$ 个大城市和 $m$ 条道路，每条道路连接这 $n$ 个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这 $m$ 条道路中有一部分为单向通行的道路，一部分为双向通行的道路，双向通行的道路在统计条数时也计为 $1$ 条。wlc决定从 $1$ 号城市出发，并最终在 $n$ 号城市结束自己的旅行。在旅游的过程中，任何城市可以重复经过多次，但不要求经过所有n 个城市。wlc是一个很精明的人，他打算在旅行中通过买卖物品，赚取差价，从而获得利益。现在我们假设，旅行中只有一种物品三国杀卡片，当然每个城市三国杀卡片的价格是不一样的。但是wlc主要是来旅游的，所以他打算只进行一次这样的买和卖。 现在给出 $n$ 个城市的三国杀卡片价格， $m$ 条道路的信息（每条道路所连接的两个城市的编号以及该条道路的通行情况）。请你告诉wlc，他最多能赚取多少钱。

####输入格式 第一行包含 $2$ 个正整数 $n$ 和 $m$ ，中间用一个空格隔开，分别表示城市的数目和道路的数目。

第二行 $n$ 个正整数，每两个整数之间用一个空格隔开，按标号顺序分别表示这 $n$ 个城市的三国杀卡片价格。

接下来 $m$ 行，每行有 $3$ 个正整数， $x,y,z$ ，每两个整数之间用一个空格隔开。

如果 $z=1$ ，表示这条道路是城市 $x$ 到城市 $y$ 之间的单向道路；如果 $z=2$ ，表示这条道路为城市 $x$ 和城市 $y$ 之间的双向道路。 ####输出格式 只需输出一个整数，表示wlc最多可以赚取多少钱。 ####样例1输入

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

####样例输出

5

####数据范围与提示

对于 $10\%$ 的数据，$n\leq 6$；

对于 $30\%$ 的数据，$n\leq 100$；

对于 $50\%$ 的数据，不存在一条旅游路线，可以从一个城市出发，再回到这个城市；

对于 $100\%$ 的数据，$1\leq n\leq 100,000，1\leq m\leq 500,000$， $1\leq x，y\leq n，1\leq z\leq 2$ ，$1\leq各城市三国杀卡片价格\leq100$。