Treasure Hunt
By Guilherme de Lima Bernardes, UNB 
Brazil
By Guilherme de Lima Bernardes, UNB Brazil
The archipelago of Nlogônia is formed by uninhabited and haunted islands. Each island has a small pier and N caves that are accessed exclusively by M secret trails. A long time ago, they were used by pirates to store jewelry, beverages and goods obtained after looting in cities and ships. With the end of this era, it is believed that there are treasures lost on some islands.
For security reasons, the pirates had a very curious method of storing their belongings. To hide a treasure, a single island was chosen. First, the area of each cave was calculated. Because they believed that prime numbers brought luck, only caves whose area value was also a prime number were chosen, in a total of K caves. The treasure was divided into K equal parts and distributed along the selected caves.
After exploring debris from an old pirate ship, Rafael found maps describing some islands where possibly treasures were hidden. As Rafael faield the algorithms course, he asked for you help to write a program in which given the characteristics of an island, you have to determine the least time possible to leave the pier, collect the treasure, which is go through all the caves containing parts from the treasure and then return to the pier.
The input is composed of several test cases. A first line of a test case with two integers N and M (1 ≤ N ≤ 100, 1 ≤ M ≤ N (N -1) / 2), respectively representing the number of caves on an island and number of secret paths. The second line consists of integers N, where the ith number Xi represents an area of the ith cave (1 ≤ Xi ≤ 10^5). You can assume there will be between 1 and 15 prime numbers. Therefore, 1 ≤ K ≤ 15. As next M three complete lines A, B and C (1 ≤ A, B ≤ N + 1, A! = B and 1 ≤ C ≤ 1000) indicating that there is a secret path between how Caves A and B and which are spent C minutes to complete the journey. The value N + 1 represents the of the island, so when A or B for equal N + 1 means that there is a path between the pier and one of the caves. You can assume that it is always possible to walk a path between any pair of caves, or between the pier and any cave.
For each test case, print out the value that represents, in minutes, the shortest possible time for Rafael to leave the island , collect the treasure, and return to the pier. You must not take in consideration the time spent by Rafael to get some of the treasure and walk through a cave.
| Input Sample | Output Sample |
|
3 4 101 95 991 1 4 20 2 3 5 4 3 20 1 2 5 2 2 1 2 1 3 15 2 1 30 |
50 90 |