题目描述
巡展路线经过 $n$ 个城市（编号 $1 \sim n$）、$m$ 条道路（单向或双向）， 各城市的纪念品价格不同（同一城市买卖同价）。 商人从城市 1 出发旅游，最终到城市 n 结束（城市可重复经过）， 途中至多进行一次"低买高卖"：在某个经过的城市买入、在其后经过的另一个城市卖出。 求最大利润；赚不到差价则输出 0。
输入格式
第一行两个正整数 $n, m$； 第二行 $n$ 个正整数，为各城市价格； 接下来 $m$ 行，每行三个整数 $x, y, z$（$z=1$ 单向 $x \to y$；$z=2$ 双向）。
输出格式
一行一个整数：最大利润。
数据范围
$$2 \le n \le 4000$$
，$$1 \le m \le 2000$$
，价格 $\le 10^9$。