题目描述

某国有 $n$ 座城市和 $m$ 条道路，每条道路连接两座城市。部分道路为单向通行，部分为双向通行（双向道路统计时计为 $1$ 条）。任意两座城市之间至多有一条直连道路。

同一种商品在不同城市的售价不同，但同一城市买入价与卖出价相同。商人小 L 从 $1$ 号城市出发，最终到达 $n$ 号城市。旅途中他可以在某个城市买入商品，之后在另一城市卖出，赚取差价作为旅费（最多进行一次交易）。城市可重复经过，目标是最大化差价收益。

请计算小 L 最多能赚取多少旅费。

输入格式

第一行两个正整数 $n$ 和 $m$，分别表示城市数和道路数。

第二行 $n$ 个正整数，按编号顺序表示各城市的商品价格。

接下来 $m$ 行，每行三个正整数 $x, y, z$。$z=1$ 表示 $x$ 到 $y$ 的单向道路；$z=2$ 表示 $x$ 和 $y$ 之间的双向道路。

输出格式

一个整数，表示最多能赚取的旅费。若无法获利则输出 $0$。

样例

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

5

提示

输入数据保证 $1$ 号城市可以到达 $n$ 号城市。

对于 $10\%$ 的数据，$1 \le n \le 6$。

对于 $30\%$ 的数据，$1 \le n \le 100$。

对于 $50\%$ 的数据，不存在从某城市出发再回到自身的路线。

对于 $100\%$ 的数据，$1 \le n \le 100000$，$1 \le m \le 500000$，$1 \le x, y \le n$，$1 \le z \le 2$，商品价格 $\le 100$。