Background

Cycle.

Problem Description

Given a directed graph $G$ with no multiple edges and no self-loops, and a sequence $\{a_n\}$, each time you may add a directed edge $i\to j$ at a cost of $a_i+a_j$. Find the minimum total cost to make it possible to find $k\geq 2$ distinct vertices $p_1,p_2,\dots,p_k$ such that for all $i\in [1,k]$, there is an edge $p_i\to p_{i\bmod k+1}$.

Input Format

The first line contains two integers $n,m$ ($2\le n\le 5 \times 10^5$, $n-1 \le m \le 10^6$), denoting the number of vertices and edges in the graph.

The second line contains $n$ integers, denoting the sequence $\{a_n\}$ ($1\le a_i\le 10^9$).

The next $m$ lines each contain two integers $u,v$ ($1\le u,v\le n$), meaning there is a directed edge $u\to v$.

Output Format

Output one integer in a single line, denoting the minimum cost.

5 5
1 2 3 4 5 
1 2
2 3
3 4
1 5
5 4 

3

Hint

Translated by ChatGPT 5