5 7
4 5 1
1 3 1
1 4 -1
1 4 -1
4 5 1
2 4 -1
4 3 -1