I. 修路

传统题

1000ms

256MiB

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

说明

给你一个无向图，这个无向图有 n

如果你要连接 x,y，那么需要花费 ax+ay 的成本。或者给你 m 条边 x,y,w，表示你如果连接 x,y需要花费 w，当然你也可以花费 ax+ay。那么请问把这 n 个点连通的最小花费是多少？

第一行输入两个整数 n,m(1 <= n ,m <= 2 * 10^ 5) ，表示 n 个顶点，m 条边。

第二行输入 n 个整数，表示顶点 i 的权值为 a_i (1≤a_i≤10^12 )。

接下来输入 m 行，每行包括三个整数 x,y,w(1≤x,y≤n,1≤w≤10^12,x≠y)，表示如果连接 x,y 需要花费 w。