Ancient Cave Expedition

A cave full of ancient treasure has been found. The treasure is worth so much that a single successful expedition would make someone the richest person alive. One lucky archaeology company took over the whole expedition, and you are an intern there.

Here is the progress so far.

• Gayoung is one of the two project leads and an expert gem appraiser. She catalogued the value of every treasure buried in the caves.
• Nahee is the other project lead. She weighed market value against expedition cost and wrote the profit each single cave can bring as one number.
• Dami joined as project manager. She ordered every piece of equipment the expedition might need, on her own judgment. She did not talk to the field team enough, so some of the machines she ordered are too large to fit into the caves and cannot be used.
• Dami was fired over that and Lara took the role. Lara ordered devices that widen a cave until Dami's machines fit through. She then asked the budget lead whether the company budget could also pay for extra equipment to pull the gear back out after the expedition.
• Mari is the budget lead. Mari refused to buy hoisting equipment out of the company budget, and Lara decided not to bring any extra equipment.
• After a long eight hour meeting the analysis was that the company budget cannot carry any more equipment. So the company will explore only the caves that pay the most according to Nahee's numbers, leave the gear behind inside the caves, and sell the exploration rights to another company in that state.
• Bada, an economics major, was hired to sell the rights. After the expedition Bada will consult her older sister Sarang, a professional dealmaker, and sell the rights for the highest price she can get.

You are the engineer Gayoung hired early in the project. Using Nahee's numbers, you now have to work out which caves to explore for the largest profit. The extra cost of widening a cave and of exploring it is already computed by Dami and Lara. The cave map was finished by the field team led by Ayoung, so it is 100% accurate.

The expedition always starts at cave 1, which is the entrance. Entering any other cave without exploring cave 1 first is impossible. Because of Mari's decision there is no equipment for moving gear back to a shallower cave, so once you enter a cave you can only continue into a cave that is deeper and directly connected to it. The route is a single strand that starts at cave 1 and only goes deeper.

Exploring cave $i$ earns $v_i$. Moving from cave $a$ into a directly connected cave $b$ costs $c$ to widen the cave and carry the gear in. The total profit is the sum of the values of the explored caves minus the sum of the costs of the tunnels you pass through. You may stop exploring at any cave, and exploring only cave 1 is allowed.

Every cave is reachable from cave 1.

The first line has the number of test cases $T$. ($1 \le T \le 10$)

The first line of each test case has the number of caves $N$ and the number of directly connected cave pairs $E$. ($1 \le N \le 2 \times 10^4$, $0 \le E \le 10^5$)

The next line has $N$ integers $v_1, v_2, \dots, v_N$, where $v_i$ is the value of the treasure obtained by exploring cave $i$. ($0 \le v_i \le 10^4$)

Each of the next $E$ lines has three integers $a_e$, $b_e$, $c_e$. Cave $a_e$ is directly connected to cave $b_e$, and widening the cave and carrying the working equipment into $b_e$ costs $c_e$. ($1 \le a_e, b_e \le N$, $0 \le c_e \le 10^4$)

In the input $b_e$ is always deeper than $a_e$. Cave numbers do not follow the order of depth. The same pair of caves can appear more than once with a different cost.

The expedition always starts at cave 1, and every cave is reachable from cave 1.

Print two lines for each test case.

On the first line print the largest profit the expedition can make and the number of caves explored on that route, separated by a space.

On the second line print that route as cave numbers in visiting order, separated by spaces.

If several routes reach the largest profit, print the route whose sequence of cave numbers comes first in lexicographic order. To compare two sequences, compare the numbers from the front; if one sequence is exactly the beginning of the other, the shorter one comes first.