9
12
0 1 140
0 8 330
1 2 380
2 3 160
3 4 195
4 5 115
3 5 375
5 6 100
6 7 115
7 8 180
8 1 150
8 4 390