A29937.最优贸易

C国有n个大城市和m条道路，每条道路连接这n个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这m条道路中有一部分为单向通行的道路，一部分为双向通行的道路，双向通行的道路在统计条数时也计为1条。

C国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。


商人阿龙来到C国旅游。当他得知同一种商品在不同城市的价格可能会不同这一信息之后，便决定在旅游的同时，利用商品在不同城市中的差价赚回一点旅费

每组输入数据的第一行包含2个正整数n和m，中间用一个空格隔开，分别表示城市的数目和道路的数目。

第二行n个正整数，每两个正整数之间用一个空格隔开，按标号顺序分别表示这n个城市的商品价格。


接下来m行，每行有3个正整数，x，y，z，每两个整数之间用一个空格隔开。如果z=1，表示这条道路是城市x到城市y之间的单向道路；如果z=2，表示这条道路为城市x和城市y之间的双向道路。





数据规模：


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


对于10%的数据，1≤n≤6。


对于30

每组输出共1行，包含1个整数，表示最多能赚取的旅费。如果没有进行贸易，则输出0。