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