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