4 10
4 1 6
4 2 2
3 4 2
2 1 7
4 3 5
2 3 5
3 2 5
1 3 8
2 4 3
2 1 7