Wouldn't a better formulation be: "Give me the shortest route with a cost of 5 or lower with the minimum fire tiles in the path necessary" Since your formulation doesn't care about the amount of fire tiles in case there is no other solution?