Input
4 4
1 4 2
1 2 0
2 3 0
3 4 0
1 4
Output
3
4
1 2 3 4
Input
4 3
1 2 4
2 3 5
3 4 6
1 4
Output
112
4
1 2 3 4
Input
4 2
1 2 0
3 4 1
1 4
Output
-1