6 9
6 1 1
6 2 7
2 1 1
1 4 2
2 4 4
1 3 3
3 4 1
3 5 6
4 5 2