Input
5 2
1 3 1
1 5 1
Output
1 2 3 0 3
Input
3 2
1 3 1
1 2 1
Output
-1
Input
10 3
4 7 2
1 10 3
8 9 1
Output
2 2 2 1 1 0 4 3 4 4