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