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