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