该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

潘皇最终还是抓到了迟到的阿冬。潘皇提出要和阿冬玩一场游戏。如果阿冬赢了，潘皇就放阿冬一马；反之，阿冬则要做他与潘皇游戏分数之差一样多的题。为了公平起见，小蔡提供了一个有趣的游戏——小菜时代，规则如下：

$1$.游戏在一张名为天下局势图的无向图上进行，图上有$N$个点，初始时每个点都对应着一座未被占领的城池。天下局势图中共有$M$条道路，城池之间由道路连接，每条道路所连接的两座城池能通过这条道路相互到达。玩家占领每座城池后能够得到这个城市的威望值$p_i$。每一条道路也拥有着相应的威望值$z_i$ ，如果一条道路连接的两座城市被同一个玩家所占领，那么这条道路的威望值也会属于该玩家。

$2$.在游戏中，阿冬和潘皇可以轮流占领任意一座未被占领的城池，同时每个玩家每一轮都必须占领一座城池。

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

考虑到阿冬迟到，因此小蔡让潘皇得到了优先占领第一座城市的权利。阿冬不想做题，潘皇想让阿冬做题，因此双方都希望自己的分数尽可能高。当然，潘皇是不可能让阿冬这么轻易地逃过一劫的，你能算一算游戏结束后阿冬需要做多少道题吗？

输入格式

第一行两个正整数$N$($ 1 \le N \le 10^4$)和$M$ ($1 \le M \le 10^5$)，分别表示天下局势图的节点数和边数。

在接下来$N+M$ 行中，前$N$行每行一个整数$p$($ -10^4 \le p \le 10^4$)，依次表示第$1$座到第$N$ 座城市的威望值。

后$M$行，每行三个整数$x,y,z$，表示存在一条威望值为$z$($ -10^4 \le z \le 10^4$)的边，连接城池$x$和城池$y$ 。

输出格式

输出一个整数，表示最终游戏结束后，潘皇的分数减去阿冬的分数是多少。

样例

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

10