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