Minimum Cost to Form a Directed Cycle

You are given a directed graph \(G\) without multi-edges and self-loops and a sequence \(\{a_i\}_{i=1}^n\) associated with the vertices. You may add an edge from vertex \(i\) to vertex \(j\) (\(i \neq j\)) at a cost of \(a_i+a_j\). Your task is to achieve a state (by possibly adding several edges) such that there exists a directed cycle containing at least two distinct vertices. In other words, you need to have \(k\ge 2\) distinct vertices \(p_1, p_2, \dots, p_k\) such that for every \(i\) with \(1\le i\le k\), there is an edge from \(p_i\) to \(p_{i\bmod k+1}\).

If the original graph already contains a cycle, the answer is 0. Otherwise, you should add the minimum cost set of edges to create a cycle. Note that although the cost formula for adding an edge is symmetric, you can only add an edge if it does not already exist in \(G\).

Hint: If there is a directed path from vertex \(i\) to vertex \(j\) in the original graph, then by adding the edge \(j\to i\) (at cost \(a_j+a_i\)) you complete a cycle.

If no such path exists between any pair (for example, in a completely disconnected graph), you can always create a 2-cycle by choosing two vertices \(i\) and \(j\) and adding both edges \(i\to j\) and \(j\to i\) at a total cost of \(2(a_i+a_j)\). The answer is the minimum cost achievable by these strategies.

inputFormat

The input consists of multiple lines:

1. The first line contains two positive integers (n) and (m), where (n) is the number of vertices and (m) is the number of edges.
2. The second line contains (n) positive integers (a_1, a_2, \dots, a_n), representing the cost values for the vertices.
3. Each of the next (m) lines contains two integers (u) and (v) (1-indexed) indicating a directed edge from vertex (u) to vertex (v).

It is guaranteed that (G) has no self-loops and no multiple edges.

outputFormat

Output a single integer which is the minimum total cost needed to ensure that the graph (with added edges) contains at least one directed cycle involving at least two distinct vertices.

sample

3 3
1 2 3
1 2
2 3
3 1

0