the shortest path has length 21
the cities on the shortest path are:
  1 8 3 5 6 2 4 7