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