Case 1:
   Distance: 173529
   Route: 6,3,4,9

Case 2:
   Distance: 45719
   Route: 1,5,4