5 3
2 7 -1000
7 1 2
6 4 -1000
6 -1000 2
1 -1000 5
2 1 5
1 2 1
2 1 5