[Usaco2008Nov]安慰奶牛cheer

Farmer John 变得非常懒，不想再继续维护供奶牛通行的道路。这些道路连接着 $N$ 个牧场，牧场编号连续，为 $1$ 到 $N$。每个牧场都是一头奶牛的家。

FJ 计划尽可能多地拆除现有的 $P$ 条道路，同时仍需保证所有牧场之间连通。因此，你首先需要决定保留哪些道路。最终必须保留恰好 $N-1$ 条道路。

第 $j$ 条双向道路连接牧场 $S_j$ 和 $E_j$，走完这条道路需要花费 $L_j$ 的时间。任意两个牧场之间至多有一条道路。

奶牛们非常伤心，因为她们的交通系统被削减了。你需要前往每一头奶牛的住处，与她们交谈并安慰她们。每次到达第 $i$ 个牧场时，无论之前是否到达过，都必须花费 $C_i$ 的时间与该牧场的奶牛交谈。

你每天晚上都会在同一个牧场过夜，这个牧场可以由你自行选择，直到所有奶牛都不再伤心。每天早晨起床时，以及晚上回到住处睡觉时，都需要与住处的奶牛交谈一次。请计算在选择保留道路以及过夜牧场均最优的情况下，安慰所有奶牛所需的最少时间。

输入格式

• 第一行包含两个整数 $N$ 和 $P$。
• 接下来 $N$ 行，第 $i$ 行包含一个整数 $C_i$。
• 接下来 $P$ 行，每行包含三个整数 $S_j$、$E_j$ 和 $L_j$，表示一条连接牧场 $S_j$ 与 $E_j$、通行时间为 $L_j$ 的双向道路。

输出格式

输出一个整数，表示安慰所有奶牛所需的最少总时间，其中包括在过夜牧场与奶牛进行的两次交谈时间。

样例输入

5 7
10
10
20
6
30
1 2 5
2 3 5
2 4 12
3 4 17
2 5 15
3 5 6
4 5 12

样例输出

176

数据范围

• $5\le N\le 10^4$；
• $N-1\le P\le 10^5$；
• $1\le S_j\le N$；
• $1\le E_j\le N$；
• $S_j\ne E_j$；
• $0\le L_j\le 10^3$；
• $1\le C_i\le 10^3$；
• 任意两个牧场之间至多有一条道路。

来源与许可

本题为 USACO 2008 November 试题「Cheer Up the Cows」，题面与测试数据整理自 BZOJ 1232。

样例 1

输入

5 7
10
10
20
6
30
1 2 5
2 3 5
2 4 12
3 4 17
2 5 15
3 5 6
4 5 12

输出

176