408051: GYM102968 A Perfect Alliance

In the AGM world there are $$$N$$$ tribes (numbered from $$$1$$$ to $$$N$$$) and $$$M$$$ directed roads between these tribes. For each tribe $$$i$$$ we know the cost $$$C_i$$$ to build a road that leaves this tribe or reaches this tribe. So, the cost to build a directed road from tribe $$$x$$$ to tribe $$$y$$$ is $$$C_x + C_y$$$.

These tribes want to make a $$$perfect\ alliance$$$. They are in a perfect alliance if and only if they can travel from any tribe to any other tribe using the directed roads. Help the tribes by calculating the minimum total cost to build some new directed roads, so that they can make a perfect alliance, and tell them what roads they need to build.

The first line of the input contains $$$2$$$ integers: $$$1 \leq N \leq 4.000$$$, the number of tribes; $$$1 \leq M \leq 20.000$$$, the number of directed roads between the tribes.

The second line contains the array $$$C$$$ of length $$$N$$$, $$$C_i$$$ being the cost to build a road that leaves or reaches the tribe $$$i$$$, $$$1 \leq C_i \leq 10^9$$$.

Each of the following $$$M$$$ lines contains $$$2$$$ integers: $$$x_i$$$ and $$$y_i$$$, representing that there exists a directed road from tribe $$$x_i$$$ to tribe $$$y_i$$$, $$$1 \leq x_i, y_i \leq N$$$.

The first line of the output should contain the minimum cost to build some new directed roads, so that you can travel from any tribe to any other tribe using the directed roads.

The second line should contain the number of new roads $$$Q$$$.

Each of the following $$$Q$$$ lines should contain $$$2$$$ integers, separated by a space: $$$x_i$$$ and $$$y_i$$$, representing a new road from tribe $$$x_i$$$ to tribe $$$y_i$$$.

6 6
2 5 3 5 2 7
1 2
1 4
4 5
5 3
5 6
6 4

12
2
3 1
2 5

7 7
2 5 2 5 2 7 8
1 2
2 3
3 4
2 4
4 1
5 6
5 7

23
3
6 3
3 5
7 1

The first example:

We can observe that after we add the roads (3, 1) and (2, 5), we can travel from any tribe to any other tribe using the roads. The cost to add the road (3, 1) is $$$C_3 + C_1 = 3 + 2 = 5$$$ and the cost to add the road (2, 5) is $$$C_2 + C_5 = 5 + 2 = 7$$$, so the total cost is $$$12$$$. This is the minimum possible cost.