题目背景

原比赛的测试数据较弱。此前的题目版本将原比赛数据放在 Subtask 0，将后来补充的 Hack 数据放在 Subtask 1。

题目描述

C 国有 $n$ 座大城市和 $m$ 条道路。每条道路连接两个城市，任意一对城市间最多只有一条道路直接相连。有些道路只能单向通行，有些则可以双向通行。统计道路数时，一条双向道路也只计一次。

C 国地域辽阔，各地的资源不同，同一件商品在不同城市的价格可能不同。在同一个城市，商品的买入价与卖出价相同。

商人阿龙来到 C 国旅游。他想利用水晶球在各地的差价，赚取一些旅费。这些城市的编号为 $1$ 至 $n$。阿龙从城市 $1$ 出发，在城市 $n$ 结束行程。他不必走遍所有城市，也可以多次经过同一座城市。

旅途中，他可以在途经的一座城市买入一个水晶球，再在之后到达的另一座城市卖掉，所得利润等于卖价减去买价。阿龙以旅游为主，因此最多进行一次这样的交易。若没有利润可赚，他可以放弃交易。

例如，下图给出了五座城市间的道路。单箭头和双箭头分别表示单向和双向道路。

设城市 $1$ 至 $5$ 的价格依次为 $4,3,5,6,1$。如果阿龙走 $1\to2\to3\to5$，他可以在城市 $2$ 花 $3$ 买入，再在城市 $3$ 以 $5$ 卖出，利润为 $2$。

他还可以走 $1\to4\to5\to4\to5$。第一次到达城市 $5$ 时以 $1$ 买入，再次来到城市 $4$ 时以 $6$ 卖出，然后返回城市 $5$ 结束旅行。这次交易的利润是 $5$。

给定各城市的价格和各条道路的通行方向，请求出阿龙最多能赚多少旅费。

输入格式

第一行给出正整数 $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$。

原题的分档数据范围如下。

NOIP 2009 提高组第三题。