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

题目描述

爱丽丝居住的城市由 $n$ 个地区构成，第 $i$ 个地区有 $p_i$ 个居民。

这些地区由 $m$ 条双向道路联接，使得对于任意两个地区可以通过这些道路相互到达。

第 $i$ 条道路连接地区 $u_i$ 和 $v_i$，经过这条道路需要花费 $w_i$ 的时间。

从一个地区经过若干条道路到达另一个地区所需的总时间为经过路径的时间的总和。

为了给居民们增加一些娱乐场所，爱丽丝打算选择一些地区建设游乐场。

但是由于经费问题，爱丽丝只能恰好选择 $2$ 个不同的地区建设游乐场，居民们会自行选择前往距离更近的游乐场。

定义某个居民产生的代价是从居住地区到达最近游乐园所在地区所需的最少时间。

定义总代价为所有居民产生的代价的总和。

爱丽丝想要让总代价尽量小，你能帮她算出总代价最小是多少吗？

输入格式

第一行输入 $2$ 个整数 $n$，$m$。表示地区数量和道路数量。

第二行输入 $n$ 个整数，第 $i$ 个数 $p_i$ 表示第 $i$ 个地区的居民数量。

接下来 $m$ 行，每行输入三个整数 $u_i, v_i, w_i$，表示地区 $u_i$ 和地区 $v_i$ 之间连接了一条需要花费 $w_i$ 时间的道路。

输出格式

输出仅一行，包含一个整数，表示最小总代价。

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

17

数据范围

• $2 \leq n \leq 300$
• $1 \leq m \leq 10^5$
• $1 \leq p_i \leq 10^5$
• $1 \leq u_i, v_i \leq n, u_i \neq v_i$
• $1 \leq w_i \leq 10^5$