the shortest path has length 18
the cities on the shortest path are:
  1 3 2 4