Car Race

A car race course is given as a directed graph. Each vertex is a checkpoint, and each directed edge is a one-way road that can be traveled only in its direction.

A race starts at checkpoint 1 and must return to checkpoint 1. After leaving checkpoint 1, the route must not visit checkpoint 1 again until it finishes.

The course satisfies these conditions.

• Among checkpoints other than 1, there is no route that starts and ends at the same checkpoint without passing through checkpoint 1.
• Checkpoint 1 can reach every other checkpoint.
• Every other checkpoint can reach checkpoint 1.

Each road has a score earned when that road is used. Find a valid route from checkpoint 1 back to checkpoint 1 with maximum total score, then output that score and route.

The first line contains the number of checkpoints N. The checkpoints are numbered from 1 to N.

The second line contains the number of roads M. Each of the next M lines contains p q r. This means there is a one-way road from checkpoint p to checkpoint q, and using that road earns score r.

N is a positive integer no greater than 1000. p and q are positive integers between 1 and N, and p and q are different. r is a positive integer no greater than 100.

Find a route with the maximum total score and output it.

On the first line, print the maximum total score. On the second line, print the checkpoint numbers on the route in order, separated by single spaces.

The printed route must start at checkpoint 1 and end at checkpoint 1. If there is more than one route with the maximum score, output any one of them.