10 12 2
1 2 1000
2 3 2000
3 10 1000
1 4 1100
4 5 1900
5 10 1100
1 6 1200
6 7 1799
7 10 1200
1 8 1300
8 9 1700
9 10 1300