1.最短时间

题目描述

有一个$n$个点，$m$条边的无向图，没有两个点是被一条以上的边所连接。现在计划除去尽可能多的边，但是还要保持图的连通性。你首先要决定哪些边是需要保留的。

接着你需要从某一个点出发（这是供你选择的），并最终回到这个点。期间，你要经过每个点至少一次。每次经过一条边需要花费$Val$时间，每次经过一个点需要$Cost$时间。请计算出此过程的最短时间。

输入格式

第一行：用空格隔开的两个整数$n$和$m$

接下来$n$行：每行包含了一个整数$Cost[i]$，表示$i$点经过的时间

再接下来$m$行：每行三个整数$x$，$y$，$Val$，表示经过连接$x$，$y$的边需要$Val$时间

输出格式

一行一个整数：表示最短时间

数据范围与提示

• 对于$30\%$的数据，满足$1 < n < 100$，$1 < m < 1000$
• 对于$100\%$的数据，满足$1 < n < 10000$，$1 < m < 100000$

样例

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