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