会议

时间限制： 1 秒
内存限制： 256 MB
输入： 标准输入
输出： 标准输出

题目描述

为了分享自己的科学成果，科学家们会聚集到国际会议上。核物理学家们也会举办这样的会议（尤其是在奥本海默时代，它们开始变得特别流行）。

已知在 $n$ 个城市中，每个城市居住着一定数量（可能为零）的核科学家。通过某些交通工具，可以在世界上的部分城市之间以一定的费用直接通行。这一次，组织会议的罗伯特·奥本海默不得不思考一个不那么科学的问题：如何最优化地将所有科学家聚集到同一个城市？

为了把所有的科学家集中到一个城市，对于不居住在会议举办城市的科学家，需要为他们购买从家乡城市到举办城市的交通票。当然，会议经费希望能花在比买票更有用的地方，因此罗伯特希望选择一个会议举办城市，使得总的科学家聚集费用最小。

请你帮他确定：如果还来得及选择任意一个城市作为举办地，那么购买所有科学家全部交通票所需的最小总费用是多少。

第一行包含两个整数 $n$ 和 $m$ ——城市数量以及城市之间直接通行的路线数量（$1 \le n \le 250$；$n - 1 \le m \le 4 \cdot 10^4$）。

第二行包含 $n$ 个整数 $c_i$ ——每个城市中居住的科学家数量（$0 \le c_i \le 10^7$）。

接下来的 $m$ 行每行描述一条直接通行路线。每条描述包含三个整数 $u_i$、$v_i$ 和 $w_i$ ——所连接的两个城市的编号以及通行的费用（$1 \le u_i, v_i \le n$；$u_i \ne v_i$；$1 \le w_i \le 10^7$）。

每条描述的通行方式允许从其中一个城市前往另一个城市，反之亦然。保证任意两个城市之间至多有一条直接通行路线，但任意两个城市之间至少存在一条（不一定直接的）路径。

输出一行一个整数——为将所有科学家聚集到同一城市所需购买所有交通票的最小总费用。