“Omnes viae Romam ducunt” 是一句古老的拉丁谚语，意为“条条大路通罗马”。在一个国家的所有地区都能通往首都，这依然是人们所期望的。

神奈川王国拥有若干城市，其中包括首都横滨。王国的交通部目前正计划建设一个高速公路网络，连接所有这些城市。

现有若干候选的高速公路路段，每一段都直接连接两个城市。高速公路网络是从这些候选路段中选出的一组路段。高速公路网络必须满足以下要求：

• 所有城市都应通过网络中的高速公路路段直接或间接地连接起来。
• 为了节省预算，应选择最少数量的路段。换句话说，高速公路网络不应是冗余的；连接任意一对城市的路径应该是唯一的。

在有限的预算下，高速公路网络应具备抵御自然灾害的能力。重点在于往返首都横滨的通达性。由于网络被设计为非冗余的，当某一路段因自然灾害而无法通行时，部分城市将无法从横滨到达。

我们希望最小化总风险严重程度，其定义如下：

王国中的城市具有不同的人口和经济规模，据此，每个城市被赋予一定的显著性值。对于给定的高速公路网络，因网络中某一路段发生自然灾害而造成的损失，估计为所有因此变得无法从横滨到达的城市的显著性值之和。

所有候选路段的自然灾害脆弱性均已评估。某一路段的风险严重程度计算为该路段的估计损失与脆弱性的乘积。整个网络的总风险严重程度估计为网络中所有路段的风险严重程度之和。

你的任务是通过合理设计高速公路网络，确定最小的总风险严重程度。

输入格式

输入包含单个测试用例，格式如下：

$n$ $m$ $p_1$ $\dots$ $p_n$ $u_1$ $v_1$ $q_1$ $\vdots$ $u_m$ $v_m$ $q_m$

前两个整数 $n$ 和 $m$ ($2 \le n \le 10^5$, $1 \le m \le 3 \times 10^5$) 分别描述了城市数量和高速公路候选路段数量。城市编号从 1 到 $n$，其中横滨编号为 1。第二行包含 $n$ 个整数 $p_1, \dots, p_n$，其中每个 $p_i$ ($1 \le p_i \le 1000$) 表示分配给编号为 $i$ 的城市的显著性值。

接下来的 $m$ 行描述了候选高速公路路段。其中第 $j$ 行包含三个整数 $u_j, v_j$ 和 $q_j$ ($1 \le u_j < v_j \le n$, $1 \le q_j \le 10^6$)，表示连接编号为 $u_j$ 和 $v_j$ 的城市的候选路段具有脆弱性 $q_j$。每对 $(u_j, v_j)$ 在输入中最多出现一次。

保证可以使用这些路段中的一部分设计出一个或多个连接所有城市的高速公路网络。

输出格式

输出一行，包含最小可能的总风险严重程度。

样例

输入 1

3 3
1 2 3
1 2 2
2 3 3
1 3 4

输出 1

16

输入 2

5 7
2 6 7 7 10
1 5 8
1 4 6
3 4 9
2 3 6
2 4 7
1 3 4
4 5 4

输出 2

210