In standard TSP you want to minimize the total length of the route. In your case you want to basically optimize two metrics: the length of the route, and how early high priority cities appear on the route. You need to put these two metrics into a single metric, and how you do that might have an impact on the algorithm choice. For example, map the city priorities to penalties, e.g.
1 -> 16
2 -> 8
3 -> 4
4 -> 2
5 -> 1
Then use as the metric you want to minimize the total sum of (city_penalty * distance_to_city_from_start_on_route). This pushes the high priority cities to the beginning of the route in general but allows for out of priority order traversal if otherwise the route becomes too long. Obviously the penalty values should be experimentally tuned.
With this metric, you can then use e.g. standard stochastic search approach --- start with a route and then swap cities or edges on the route in order to decrease the metric (use simulated annealing or tabu search).