Problem G

In this problem, you're to implement an automatic solver, to the game of 999: Nine Hours, Nine Persons, Nine Doors. However, the rules might be a bit different from the original game, so please read carefully!

Disclaimer: No no no, please do NOT read the wiki for an introduction, if you want to try this awesome game yourself, because that page contains spoilers!!! However, don't skip this problem! The information below has nothing to do with the plot, and will be given to the players at the beginning of the game, so you can still enjoy this game after solving this problem.

There is a mysterious maze, with n rooms and m corridors connecting them. Some corridors have a big door with a digit (1~9) written on it. Each corridor is one-way, so each door can be opened in exactly one side. Nine people, who numbered 1 to 9, are standing in room 1 when the game begins. The goal of this game is to escape the maze from the exit, which is located in room n.

There are some rules to follow:

• Each door can be used exactly once. When the door is closed again, it's locked forever.
• Each door can be opened by a group of 3~5 people. However, the sum of the numbers of these people should have a digit root equal to the digit written on the door (The digit root of an integer can be obtained by repeatedly sum up all its digits, until it becomes a single digit). For example, people 3, 5, 6, 8 can open door 4, because the digit root of 3+5+6+8=22 is 2+2=4.

Please maximize the number of people who reached room n (the exit). Note that it's allowed to visit a room multiple times, including room n. However, once you escaped, you cannot go back into the maze again.

Input

There are multiple test cases. Each test case begins with two integers n, m (2<=n<=10, 1<=m<=10). Each of the next m lines contains 3 integers u, v and d to describe a corridor from room u to room v, with a door of digit d. If d=0, that means there is no door in this corridor. There can be multiple corridors connecting the same ordered pair of rooms, but no corridor can connect a room to itself.

Output

For each test case, print the maximum number of people who can escape, followed by all possible combinations of the people who escaped. Each combination is string of digits, representing the escaped people. The digits within each combination should be sorted in ascending order, and all the combinations should also be sorted in ascending order (lexicographically).

Sample Input

2 1
1 2 9
5 10
1 2 4
1 2 5
2 3 3
2 3 7
2 3 8
3 4 1
3 4 2
3 4 6
4 5 9
4 5 9
3 3
1 2 1
2 3 2
3 2 0
3 4
1 2 1
2 3 2
2 3 2
3 2 0
4 3
1 2 1
2 3 2
3 4 3
4 3
1 2 1
2 3 2
3 4 6

Output for Sample Input

5 12348 12357 12456 12789 13689 14589 14679 15678 23589 23679 24579 24678 34569
34578
9 123456789
4 1235 1379 1469 2369 2459 2567 3467
5 12358 12367 13789 23689 25678
0
3 123 249 267

Hint

If you got time limit exceeded, that usually means you should change your algorithm or use some techniques to avoid unnecessary calculations. Don't make your solution too complicated, though. It's not intended to be a hard problem. Only very conventional techniques are involved.