6 9
1 2 1
2 3 9
1 3 12
2 4 3
4 3 4
3 5 5
4 5 13
5 6 4
4 6 15