I now one greedy solution, which gets AC.
Please, add this test:
7 1
1 2 2
2 5 1
2 6 1
1 3 1
3 7 2
3 4 2

answer: 2