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 (->).
*CodeQuest does not actually have national finals
## Input
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".
## Output
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 (->).
[samples]
## Note
*CodeQuest does not actually have national finals
**Definitions**
Let $ G = (V, E) $ be a directed graph where:
- $ V $ is the set of cities (including "Syracuse" and the target location $ s $).
- $ E \subseteq V \times V \times \mathbb{Z}^+ $ is the set of flights, where each edge $ (u, v, p) $ represents a flight from city $ u $ to city $ v $ with price $ p $.
Let $ b \in \mathbb{Z}^+ $ be the budget constraint.
**Constraints**
1. Start at "Syracuse", end at $ s $, then return to "Syracuse".
2. Total price of the round-trip route $ \leq b $.
3. All flights are direct (no layovers).
4. At least one outbound flight from "Syracuse" and one inbound flight to "Syracuse" exist.
**Objective**
Find a round-trip path $ P = (Syracuse \to \dots \to s \to \dots \to Syracuse) $ such that:
- The total price $ \sum_{e \in P} p_e \leq b $,
- The number of flights $ |P| $ is minimized,
- Among all minimal-length paths, choose the one with minimum total price.
If no such path exists, output "IMPOSSIBLE".
Otherwise, output:
- $ n $: number of flights in $ P $,
- $ t $: total price of $ P $,
- Then, $ n $ lines of the form $ u \to v $ for each flight in $ P $, in order.