favorite We need a little bit of your help to keep things running, click on this banner to learn more

Shortest paths - interesting graph problems


Some planets of the galaxy, where Peter Pyatochkin recently moved, are connected with portals. If planets A and B are connected, it means that each planet has a special device - portal - for teleportation between them. The creature that enters the portal on the planet A, instantly appears on the planet B and vice versa.

The same portal can not be used to teleport to different planets. If some pair of planets are not connected yet, they can be united, but a new portal must be built on each planet. Building portals requires considerable outlay and can cost differently on different planets.

We say that there is a teleport way between two planets, if you can get from one planet to another, teleporting one or more times (using intermediate planets). Unfortunately, there is no teleportation way between any two planets.

You are given the communication scheme among the planets and the cost of the portal on each planet. Determine the lowest amount of money you need to spend to ensure the existence of a teleportation path between each pair of planets in the galaxy.


The first line contains two integers: the number of planets in the galaxy n (n1000) and the number of planets pairs m, directly connected with portals.

Second line contains n positive integers p1, p2, …, pn - the cost to build a new portal, respectively on the first, on the second, ...., on the n-th planet. None of the costs exceed 106.

Each of the next m lines contains two positive integers ai and bi (1ai < bin, 1im) that describe the pair of connected planets. Each pair is given in input only one time.


Print the smallest amount of money that should be spent on the portals construction on some planets so that there would be the teleportation path between each pair of planets in the galaxy.

Time limit 1 second
Memory limit 128 MiB
Input example #1
4 2
7 4 7 3
1 3
2 4
Output example #1
Input example #2
8 5
3 7 5 7 8 12 6 9
4 5
5 6
8 7
1 2
3 1
Output example #2

Example description: Its possible to connect the forth planet either with first, or with third, satisfying the problem conditions and spending 3 + 7 = 10 money. To use less money is impossible

Author Danylo Mysak
Source ІІІ (городской) этап Всеукраинской олимпиады школьников по информатике, 2013, г. Киев