407072: GYM102697 043 Low-Budget Flight Paths

Your team qualified for the national finals of CodeQuest 2021*, and you need to figure out which flights you need to take to get to the location of the finals. However, you have a limited budget for the whole trip. Figure out the best route for your team to go to the specified location of the competition, given the possible flights and their times. If multiple routes are possible, choose the one that has the lowest price. Assume there are no layovers in airports, i.e. all of the time spent on a journey is spent on the airplanes. Your starting location is always "Syracuse"

The first line of input contains a string $$$s$$$: the location of the CodeQuest competition. The next line contains two space-separated integers $$$n$$$ and $$$b$$$: the number of flights, and your total budget, respectively. The next $$$n$$$ lines each describe one flight. Each line contains three space-separated items: two strings, representing the start and end cities of the flight, and one integer, representing the price. There will always be at least one flight departing from "Syracuse", and at least one flight arriving in "Syracuse".

If it is impossible to go to the CodeQuest finals and back with your budget, output "IMPOSSIBLE" (without the quotes). Otherwise, output two space-separated integers $$$n$$$ and $$$t$$$: the number of flights that you need, and the total price, respectively. Then, output $$$n$$$ lines, each containing the start and end cities of each flight that you are going to take, separated by an arrow (->).

SanFrancisco
9 120
Syracuse NewYork 5
Syracuse Detroit 5
Syracuse Atlanta 20
Atlanta Dallas 50
Dallas SanFrancisco 30
Detroit Chicago 1
Chicago SanFrancisco 30
SanFrancisco NewYork 10
NewYork Syracuse 10

5 56
Syracuse -> Detroit
Detroit -> Chicago
Chicago -> SanFrancisco
SanFrancisco -> NewYork
NewYork -> Syracuse

NewYork
3 10
Syracuse Detroit 9
Detroit NewYork 1
NewYork Syracuse 2

IMPOSSIBLE

SanFrancisco
8 1000
Syracuse SanFrancisco 100
NewYork StLouis 5
StLouis Portland 5
Syracuse NewYork 5
Portland LosAngeles 5
LasVegas SanFrancisco 5
LosAngeles LasVegas 5
SanFrancisco Syracuse 1

7 31
Syracuse -> NewYork
NewYork -> StLouis
StLouis -> Portland
Portland -> LosAngeles
LosAngeles -> LasVegas
LasVegas -> SanFrancisco
SanFrancisco -> Syracuse

*CodeQuest does not actually have national finals