题目背景

译自 ICPC 2024 Yokohama Regional Contest。

题目描述

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

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

有许多候选的高速公路路段，每个路段都直接连接两个城市。高速公路网络是从候选路段中选出的一组高速公路路段。高速公路网络需要满足以下要求:

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

在有限的预算下，高速公路网络应能抵御自然灾害。重点放在与首都横滨之间的可达性上。由于路网没有预留冗余，当一个路段因自然灾害而无法使用时，一些城市将无法从横滨到达。

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

王国中的城市拥有不同的人口和经济规模，基于此，这些城市被赋予了特定的重要度。给定一个高速公路网络，网络中单个路段因自然灾害而遭受的损失定义为，这个路段无法通过时，从横滨无法到达的城市的重要性值之和。

我们评估了所有候选路段的脆弱度。一个路段的风险严重度，定义为损失与脆弱度之积。网络的总风险严重度，估算为网络中所有路段的风险严重度之和。

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

输入格式

仅一组数据，格式如下所示：

$n$ $m$
$p_1$ $\dots$ $p_n$
$u_1$ $v_1$ $q_1$
$\dots$
$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)$ 在输入中最多出现一次。保证可以使用其中一些路段设计一个或多个连接所有城市的高速公路网络。

输出格式

输出一行一个整数，即最小的可能总风险严重程度。

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

16

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

210