星际之路求解

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

已知宇宙中有 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