好的，我已经把题目整理成清晰的形式，包含样例解释，适合直接上传到算法平台。

题目描述

C 国有 $n$ 个大城市和 $m$ 条道路，每条道路连接两个不同城市。
任意两个城市之间最多只有一条道路直接相连。
道路可能是单向的或双向的（双向道路在计数时算作 $1$ 条）。

每个城市的水晶球价格不同，但同一个城市的买入价和卖出价相同。
商人阿龙从 $1$ 号城市出发，最终到达 $n$ 号城市（可以重复经过城市）。
他可以选择在某个城市买入水晶球，在之后经过的另一个城市卖出水晶球，赚取差价。
整个旅行过程中，他最多进行一次买卖（也可以不进行买卖，旅费为 $0$）。

请你计算他最多能赚多少旅费（即最大差价）。

输入格式

第一行两个整数 $n, m$，表示城市数与道路数。
第二行 $n$ 个正整数，表示每个城市的水晶球价格。
接下来 $m$ 行，每行三个整数 $x, y, z$：

• 如果 $z=1$，表示城市 $x$ 到 $y$ 的单向道路。
• 如果 $z=2$，表示城市 $x$ 和 $y$ 之间的双向道路。

输出格式

一个整数，表示最大旅费（最大差价，可为 $0$）。

数据范围

• $1 \le n \le 10^5$
• $1 \le m \le 5 \times 10^5$
• $1 \le 商品价格 \le 100$

输入样例

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

输出样例

5

样例解释

城市数 $n=5$，道路数 $m=5$。
各城市水晶球价格：
城市 1: 4
城市 2: 3
城市 3: 5
城市 4: 6
城市 5: 1

道路：

1. 1→2 单向
2. 1→4 单向
3. 2↔3 双向
4. 3→5 单向
5. 4↔5 双向

阿龙要从 $1$ 到 $5$，可以重复经过城市。
目标：在某个城市买入，在之后某个城市卖出，差价最大。

可行路径示例：
$1 \to 2 \to 3 \to 5$

• 在 2 号城市买入（价格 3）
• 在 3 号城市卖出（价格 5）
• 差价 $5 - 3 = 2$

更好的路径：
$1 \to 4 \to 5$

• 在 5 号城市价格 1，买入？ 但必须先买后卖，所以如果在 5 买，后面没有城市可以卖（因为价格都比 1 高吗？不一定）
  仔细分析：
  经过顺序 $1 \to 4 \to 5$，可以在 4 买（价格 6），在 5 卖（价格 1），亏钱。不行。
  但可以在 5 买（价格 1），再走到 4 卖（价格 6）吗？
  路线 $1 \to 4 \to 5 \to 4$：在 5 买，然后回到 4 卖，差价 $6-1=5$，且确实从 1 出发最终到 5 吗？
  $1 \to 4 \to 5 \to 4 \to 5$：起点 1，终点 5，中间可以在 5 买，在 4 卖吗？
  不行，必须先经过买点，再经过卖点。
  所以如果 $1\to 4\to 5\to 4\to 5$，买在 5，卖在 4，这是回到之前经过的城市卖，允许吗？
  允许（因为城市可以重复经过），且 4 在路线中出现在买点 5 之前？不，路线是 1→4（第一次经过）→5（买）→4（第二次经过，卖）→5（结束）。
  卖点 4 在买点 5 之后出现（在路径顺序上），所以合法。

但是这样最终终点是 5，所以从 1 到 5 的路径上，可以绕路去低价城市买，再去高价城市卖。

实际上最优是：
路径 $1\to 2\to 3\to 5\to 4\to 5$

• 在 5 买入（价格 1）
• 在 4 卖出（价格 6）
• 差价 $6-1=5$
  可行，因为路线从 1 出发，先到 5，再到 4，再回到 5 结束。
  检查连通性：
  1→2→3→5 可行（通过道路 1→2, 2→3, 3→5）
  5→4 可行（4↔5 双向）
  4→5 可行。
  因此总路径：1→2→3→5→4→5，买在 5，卖在 4，差价 5。

没有更大的差价，因为最低价城市 5 价格 1，最高价城市 4 价格 6，差价 5，且可以按上述路径实现。

输出：5