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