8 7 6
1 2 10
2 3 15
3 4 1
4 5 12
5 6 13
6 7 123
7 8 10
0