Route #1: 2 Route #2: 6 Route #3: 8 Route #4: 15 12 10 Route #5: 14 5 Route #6: 13 9 7 Route #7: 11 4 Route #8: 3 1 cost 450