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