404041: GYM101401 E Roads (B)

Some cities are now occupied. Mr. Light wants to cut all paths that go between specific pairs of cities. Destroying any road on a path cuts that path. The cost of destroying each road d_i is given.

Mr. Light already destroyed some (one or more) roads, and the cost for the destroyed roads is given as zero. Find the minimum total cost needed to cut all the paths between the given pairs of cities.

The first line of input contains two space-separated integers N, M (3 ≤ N ≤ 2 × 10⁵) , the number of cities and the number of pairs to cut the paths between them, respectively.

The second line of input contains N space-separated integers d_i (0 ≤ d_i ≤ 10⁹), the i^th value represents the cost of destroying the i^th road (or 0 if it is already destroyed).

It is guaranteed that at least one of the roads is already destroyed.

Each of the following M lines contains two space-separated integers u, v (1 ≤ u, v ≤ N) (u ≠ v), representing a pair of cities that should not remain connected. No pair of cities will appear more than once.

Print the minimum cost on a single line.

4 2
1 0 1 1
1 4
2 3

1

8 5
4 0 5 4 5 6 3 0
1 8
3 6
5 8
8 4
4 1

5