在遥远的未来，人类已经开启了星际殖民时代，各个星球之间通过星际航道相互连接，形成了庞大的星际贸易网络。然而，由于不同星球的资源稀缺程度、科技发展水平以及市场需求各不相同，同一种稀缺物资在各个星球上的收购价和出售价存在巨大差异。星际商人卡尔听闻此讯，决定驾驶他的星际飞船穿梭于各个星球之间，利用物资的价格差赚取丰厚的利润，以升级他的飞船装备。

已知宇宙中有 $n$ 个宜居星球和 $m$ 条星际航道，每条星际航道连接这 $n$ 个星球中的某两个星球。任意两个星球之间最多只有一条直接相连的航道。这 $m$ 条星际航道中，一部分仅允许单向通行，用于快速运输物资到急需的星球；另一部分为双向通行，方便贸易往来，双向通行的航道在统计条数时同样计为 $1$ 条。

各个星球的发展状况迥异，使得同一种稀缺的能量矿石在不同星球上的交易价格截然不同。并且，在同一个星球上，买入和卖出这种能量矿石的价格始终是一致的。

卡尔计划从 $1$ 号星球出发，最终抵达 $n$ 号星球结束此次星际贸易之旅。在旅途中，任何星球都可以多次停靠补给、交易，但不要求必须经过所有的 $n$ 个星球。卡尔决定最多只进行一次能量矿石的买卖交易，毕竟飞船的载货空间有限，且他主要目的还是前往 $n$ 号星球探索神秘遗迹，若不能赚取差价，他便不会进行此次交易。

假设: 宇宙中有 6 个宜居星球，星球的编号以及星际航道连接情况如下图所示，单向箭头代表这条航道是单向通行，双向箭头表示这条航道为双向通行。 假设 $1 - n$ 号星球的能量矿石价格分别为 $8, 5, 10, 12, 3, 15$ 。 卡尔可以选择如下一条路线：$1 \to 2 \to 3 \to 6$ ，并在 $2$ 号星球以 $5$ 的价格买入能量矿石，在 $3$ 号星球以 $10$ 的价格卖出，赚取的利润数为 $5$ 。 卡尔也可以选择如下一条路线：$1 \to 4 \to 6 \to 4 \to 6$ ，并在第 $1$ 次到达 $6$ 号星球时以 $15$ 的价格买入能量矿石，在第 $2$ 次到达 $4$ 号星球时以 $12$ 的价格卖出，亏损 $3$ ，但根据规则不进行交易，利润记为 0 。

输入说明(*)

第一行包含 2 个正整数 $n$ 和 $m$ ，中间用一个空格隔开，分别表示星球的数目和星际航道的数目。 第二行 $n$ 个正整数，每两个整数之间用一个空格隔开，按标号顺序分别表示这 $n$ 个星球的能量矿石价格。

接下来 $m$ 行，每行有 3 个正整数 $x,y,z$，每两个整数之间用一个空格隔开。如果 $z=1$ ，表示这条星际航道是星球 $x$ 到星球 $y$ 之间的单向航道；如果 $z=2$ ，表示这条星际航道为星球 $x$ 和星球 $y$ 之间的双向航道。

输出说明(*)

一个整数，表示最多能赚取的利润。如果没有进行贸易，则输出 0 。

样例输入1

6 7

8 5 10 12 3 15

1 2 1

1 4 1

2 3 2

3 6 1

4 6 2

2 5 1

5 3 1

样例输出1

5