T536353 「YAC Round 11」梦违科学世纪


莲子和梅莉都是秘封俱乐部的成员。有一天，梅莉做了一个梦，她在梦境中看到了 $n$ 个世界，其中第 $i$ 个世界的结界强度为 $a_i$。 这 $n$ 个世界之间存在一些单向通道连接，你可以将其构成的网络看成一张有向图（保证无重边无自环），莲子和梅莉可以通过这些通道到达其他世界。 莲子和梅莉每次可以花费 $a_i + a_j$ 的代价构建一条 $i \rightarrow j$ 的通道。 她们想要花费 **最小** 的代价，使得可以找到 $2$ 个不同的世界 $u$ 和 $v$，满足 $u$ 和 $v$ 可以相互到达。

第一行输入两个整数 $n,m$ （$2\le n\le 5 \times 10^5$，$n-1 \le m \le 10^6$），分别表示世界的个数和通道数。 第二行输入 $n$ 个整数 $a_1, a_2, \ldots, a_n$ （$1\le a_i\le 10^9$），表示每个世界的结界强度。 接下来 $m$ 行，每行两个整数 $u,v$（$1\le u,v\le n$），表示存在一条单向通道 $u\to v$。

输出一行一个整数，表示花费的最小代价。

### 样例解释 存在两种花费最小代价的方案。 方案1: 构建一条 $3 \rightarrow 1$ 的通道，最小花费代价为 $a[3] + a[1] = 1 + 2 = 3$ 方案2: 构建一条 $4 \rightarrow 3$ 的通道，最小花费代价为 $a[4] + a[3] = 2 + 1 = 3$