input:

2
4 6
1 2 1
1 3 2
2 3 1
2 4 2
3 4 1
1 4 4
6 11
1 2 9
2 3 12
3 4 3
4 5 5
5 6 10
6 1 22
2 4 9
3 6 1
4 6 5
2 5 2
3 5 8

output:

3
1 3 4 
6
1 2 5 4 3 6 

result:

wrong answer Contestant's path is not optimal lexicographically (test case 2)