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