SPOJ in Gyumri

   You’re an intern at Greedy Cave Plundering Corporation. Your new job is to help with one of GCPC ’s projects: extracting valuable gemstones from a network of connected caves. The history of the project so far:

• Tom, one of the project managers, has hired Jill, a gemstone expert. She has already surveyed these caves and determined the value of all gemstones in each cave.

• Ruby, another project manager (PM), has been busy “guesstimating” a time frame, the budget and possible profits for this project.

• Evelyn and Jerry (also PMs) have hired two cave diggers and instructed them to extract the gemstones.

• The cave diggers needed equipment to extract the gemstones and transport them to the surface. So Jimmy (another PM) ordered some machines. Sadly, he did not communicate well with the cave diggers - he bought machines that are way too big for the current passage ways between caves.

• To fix this, Jimmy was fired and James, his successor, has ordered a very big drilling machine, so the cave diggers can widen the passage ways. However, James was fearful of cutting into his salary bonus, so he bought the cheapest machine he could find. Soon, after widening the passage way from the surface into cave 1, the cave diggers found out that the new drilling machine is very heavy and not so powerful, so it can only be used to widen a passage way that goes downwards. Once it has reached a lower cave, it can not be carried back up because of its weight.

• This is when Alice, the project manager in charge of budget planning, announced she would ignore further requests for more equipment.

• In an eight hour meeting discussing the problems of the project, it was decided to limit the project expenses. So, if further drilling would hurt profits or if the drilling machine reaches a cave where it can not go on, it will just be abandoned. Using the other machines, the cave diggers will then be able to harvest at least some of the gemstones. Afterwards, the dig site will probably be sold to another company. Ruby is already thinking about hiring her brother as a sales expert...

   This is where you come in. Tom has hired you to determine which passage ways should be widened and thereby which caves should be visited to maximize profits. Widening a passage way requires energy, materials and so on. You have to consider these costs. You will be given a map of all caves and passage ways. The map was created by the cave diggers, so it should be accurate. It contains only passage ways the drilling machine can handle, including the correct drilling direction. All caves in the map are reachable from cave one.

Input

   The input starts with a line containing T , the number of test cases (1 ≤ T ≤ 10).

   Each test case starts with a line containing two integers: N , the number of caves, and E, the number of passage ways (1 ≤ N ≤ 2 · 10⁴; 0 ≤ E ≤ 10⁵).

   The second line contains N integers v₁ v₂ . . . v_N . v_i describes the value of all gemstones in cave i (0 ≤ v_i ≤ 10⁴).

   Each of the next E lines contains three integers: a_e b_e c_e. Such a line represents one of the possible direct passage ways from cave a_e to cave b_e, widening this passage way will cost c_e (1 ≤ a_e, b_e ≤ N ; 0 ≤ c_e ≤ 10⁴). It is guaranteed that the input contains only valid digging directions, i.e. cave b_e will be strictly deeper than a_e.

   You always start from cave number 1, because the digging machine is already there and there are no caves above.

Output

   Output two lines for every test case. In the first line print two integers P and C, where P is the profit of the best possible route from top to bottom and C is the number of visited caves on that path. In the second line print the IDs of those caves, ordered from top to bottom.

   If there are multiple solutions with optimal profit, print any.

Examples