It is 8282 AD and the Bizz and the Pezz are two allied kings in the Far Far Away island, which consists of many territories some of them connected to each other with some roads. Recently, they found that a group of criminals under leadership of MijIT Dozddar want to begin two simultaneous insurrections in their territories. Therefore, they tried to recognize these criminals, but they did not succeed. Now, they have another plan for preventing the insurrections. They know the criminals must be in contact for simultaneous insurrections and by preventing them contact each other, they can prevent insurrection. In addition, they know their soldiers can identify these criminal outside of their territories. So, by building a tower in another territory (a territory except than Bizz’s or Pezz’s territory), soldiers of this tower can recognize criminals and the criminals cannot pass this territory to contact. To convince the king of a territory for building a tower in his territory, both of them must send one carrier with one letter to her/him to request for construction permission of the tower. Also, the carrier of this letter must not enter a territory more than once since the criminals may catch her/him. In addition, the carrier of the letter must pay some money in some territories when he enters them and he earns some money when he enters some other territories under indirect control of Bizz or Pezz. Of course, since the territories under control of Bizz or Pezz are few, the money carrier earns is always less than or equal to the money he must pay. It should be noted that if one starts from a territory, visits some other territories and goes back to the first territory, he does not have more money than before starting the trip. Now, Bizz and Pezz need your help to select some territories for building some towers such that the criminals of their territories could not contact each other and the total money required for sending the letters to these territories be minimum. Input The input begins with a positive integer T showing the number of test cases and then, T test cases follow. Each test case begins with a line containing two integers 2 ≤ n ≤ 50 and 0 ≤ m ≤ 300 showing the number of territories and roads between them respectively. Bizz is in territory 1 and Pezz is in territory n. After that, a line with n − 2 real numbers come where the ith one shows the amount of money the carrier must pay in the territory i + 1 (which can be negative if the territory is under indirect control of Bizz or Pezz). Then, m lines come containing two integer between 1 and n describing endpoints of a road. There is a blank line after each test case. Output For each test case, your program must output the minimum money required for sending the letters if Bizz and Pezz can prevent insurrections with their new plan rounded to four digits after fraction point, and otherwise a line containing ‘No Solution!’. Sample Input 1 78 10.0 5.0 -3.0 6.0 6.0 12 23 34 45
2/2 53 37 16 67 Sample Output 28.0000