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