10 3
1 2 1
2 4 5
3 5 6