10 10 11 70000
1 2 10000
2 3 10000
3 4 10000
4 5 10000
5 6 10000
6 7 10000
7 8 10000
8 9 10000
9 5 10000
5 7 10000
6
5
4
7
7
8
9
3
2
1
10