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