ro

In Romania there are N cities interconnected by M freeways. A freeway connects exactly 2 cities (e.g. the Bucharest-Piteşti or Bucharest-Constanţa freeways). All freeways are open to two-way traffic and one can go from any city to any other city using existing freeways. As a result of European Union accession, the government will have to take measures to respect European regulations regarding road infrastructure. These rules specify that at least one of the 2 cities between which there is a freeway has to have the rank of European capital. Initially, none of the N cities has the rank of European capital and we know for each of them the amount required in (in millions of Euro) to be modernized and promoted to said rank.
Seeing as the government's funding is limited, determine the minimum total amount the government will have to spend to promote some cities to European capital rank so that European regulations regarding road infrastructure be respected.
In order to solve this problem you have additional information available to you on behalf of the government, namely: whichever way we choose a subgroup of 14 cities of the N, there is in this subgroup at least one pair of cities, A and B, with the property that there is a city C which is not A or B (not necessarily from the selected subgroup) so that, if road would be closed both ways on all freeways that have an extremity in C, then there will not be a road between cities A and B using the freeways that are still open for traffic. This condition can be rephrased as follows: If we look at Romania's road infrastructure as a non-oriented connex graph with N nodes and M edges, any by-connex component of this graph contains no more than 13 nodes.

Input Data

Input file ro.in contains on line one integers N, M separated by a space, representing the number of cities and the number of freeways. The following line contains N integers Si (i from 1 to N) , each separated by a space, representing the amount of money necessary to promote each city i (i from 1 to N) to the rank of European capital. The following M lines each contain 2 distinct integers separated by a space, U and V, with the meaning that there is a freeway between city U and city V.

Output Data

Output file ro.out will contain on line one the minimum amount which the government has to pay to respect European road infrastructure regulations. On line two you will display an integer O, representing the number of cities promoted to the rank of European capital. Line three of the file will contain O distinct integers between 1 and N, each separated by a space, representing the cities which were selected for promotion to European capital rank.

Constraints and Statements

Example
ro.in ro.out

15 21
9 8 7 100 99 2 3 8 4 6 7 2 1 6 2
1 2
2 4
4 5
5 6
2 6
1 5
4 3
3 7
7 9
9 8
8 4
4 7
3 9
5 10
10 13
5 12
12 13
12 15
12 14
15 14
13 11

 129
9
1 4 6 7 9 10 12 13 15

Time limit: 1.3 seconds/test
Total available memory: 30 MB, of which 1 MB for the stack.


assistant Mugurel Ionut Andreica
Bucharest Polytechnic University, Automatics and Computers Department
mugurel_ionut@yahoo.com