题目描述

​ 众所周知小菜非常喜欢创造各种奇怪的游戏。某日小菜在学习图论的时候灵感突发，想到了一个精妙绝伦的趣味博弈游戏——二分天下。小菜找来了小蔡一起玩这个有趣的游戏，游戏的规则是这样的：

​ $1$ 、这个游戏在一张带权图$G$ 上进行。这是一张天下局势图，游戏伊始，图上的每个点都对应着一座未被占据的城池。玩家占领每座城池后都能够得到这个城市的威望值$Prestige(i)$。天下局势图中共有$M$条道路，城池之间由道路连接，每条道路所连接的两座城池能通过这条道路相互到达。而每一条道路也拥有着相应的威望值$Edge(j)$ ，如果一条道路连接的两座城市被同一个玩家所占领，那么这条道路的威望值也会属于那个玩家。

​ $2$ 、在游戏中，小菜和小蔡可以轮流占据任意一一座城池，已经被占领过的城市就无法再次被占领，同时每个玩家每一轮都必须占领一座城市。

​ $3$ 、小菜当然是一个公平又善良的人，为了充分保障游戏的公平和玩家的游戏体验，天下局势图中的城池数量$N$ 必定为偶数座。

​ 考虑到小菜比小蔡更帅的缘故，小菜得到了优先占领第一座城市的权力。他们两个当然都不想让对方获得胜利，因此都希望自己的分数能够比对方来的多得多得多。因此两人在游戏中都是采用最优策略的，聪明的小菜想考考不是很聪明的你：最终游戏结束后，小菜的分数减去小蔡的分数是多少。

输入格式

​ 输入的第一行包含两个正整数$N$和$M$，分别表示天下局势图的节点数和边数。

​ 在接下来$N+M$ 行中，前$N$行每行一个整数$p$，依次表示第$1$座到第$N$ 座城市的威望值。

​ 后$M$行，每行三个整数$x，y，z$，表示一条威望值为$z$的边，连接城池$x$和城池$y$ 。

输出格式

​ 输出仅包含一个整数，表示最终游戏结束后，小菜的分数减去小蔡的分数是多少

输入输出样例

输入

6 2
6
3
-1
-2
-7
10
1 2 1
1 4 5

输出

10

数据范围

$n<=10^4$，$m<=10^5$