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