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