You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

AiraKeq 正驾驶飞船穿越 C 星系。summerrain 已经先一步抵达了 $n$ 号星球，正等着和他会合。

题目描述

C 星系有 $n$ 颗星球和 $m$ 条航线。任意两颗星球之间至多有一条直接航线，双向航线也只算一条。航线可能是单向的，也可能是双向的。

同一颗星球上，星石的买入价和卖出价相同；不同星球的价格可能不同。

AiraKeq 从 $1$ 号星球出发，在 $n$ 号星球结束旅行。旅途中可以多次经过同一颗星球，也不要求走遍所有星球。

他想用飞船上的积蓄做一笔小买卖：先在某个星球买入一块星石，之后在另一颗星球卖出，赚取差价，好给 summerrain 买一份礼物。他最多只能进行一次交易，也可以选择不交易。

给出所有星球的星石价格和航线信息，求 AiraKeq 能获得的最大收益。

输入格式

第一行两个正整数 $n,m$。

第二行 $n$ 个正整数，依次表示 $1$ 到 $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$ 号星球出发，经 $2$、$3$ 号星球到达 $5$ 号星球：在 $2$ 号星球以 $3$ 买入，在 $3$ 号星球以 $5$ 卖出，收益为 $2$。

走 $1 \to 4 \to 5 \to 4 \to 5$：在 $5$ 号星球以 $1$ 买入，第二次到达 $4$ 号星球时以 $6$ 卖出，收益为 $5$。

数据范围

$1 \le n \le 100000$，$1 \le m \le 500000$，$1 \le x,y \le n$，$1 \le z \le 2$，每颗星球的星石价格不超过 $100$。

保证 $1$ 号星球可以到达 $n$ 号星球。

题目来源：NOIP 2009 提高组。