Every Santa Claus wants to surprise children with his presents. This year Santa Claus Petrovich wants to surprise children of remote Cuckooland. He is sure that in order to make a real impression he should choose a route without repeating towns. In order to bring as much happiness as possible, he plans to visit the most populated places. Petrovich took a map of Cuckooland and connected with lines some pairs of towns where, he's sure, people will wait for him. He decided not to fly between towns that are not connected. It turned out that if Petrovich can fly (using one or several flights) from town i to town j, then there is exactly one way to do this. Petrovich can start his trip in any of the towns.

Petrovich knows that when he arrives in town i, the population feels happiness A_i. And when Petrovich flies from town i to town j, he bestows happiness C_ij. The same amount of happiness is bestowed if he flies from j to i. Help Santa Claus Petrovich to maximize the amount of happiness that he can bring to people.

The first line contains the number N (1 ≤ N ≤ 50000) of towns in Cuckooland and the number K of pairs of towns that are connected. The second line contains numbers A_i (i = 1..N); A_i ≤ 10000. Each of the following K lines contains three numbers a, b, c, which mean that when Petrovich flies from town a to town b he brings happiness c (a ≠ b; c ≤ 10000). All numbers in the input are whole and nonnegative.

The first line of the output must contain the maximal amount of happiness felt by the people of Cuckooland. The second line must contain the length L of the optimal route of Santa Claus Petrovich. The third line must contain the optimal route (L numbers separated with a space). If there are several answers, you may output any of them.