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