Brightline - Back to the Future

Many UCF programming team coaches are getting old and want any way to regain their youth. A new train, the Brightline, has arrived in town. Rumor has it that a person who rides some of the trains can get younger.

Brightline runs two types of trains: the blue line and the red line. On a blue line, passengers age by a set amount of time. On a red line, passengers go back in time by a set amount of time.

Each line is directed. It connects a source city to a destination city, is labeled red or blue, and has a positive integer giving the number of minutes a passenger ages (blue) or moves back in time (red) when taking that line. Whenever you arrive in a city, you can immediately take any train leaving that city.

The system does not allow unlimited travel back in time. There is no way to start at any city and return to that same city younger than you were when you started.

All of the coaches live in Orlando, which is city 1. Given the list of all Brightline lines, find every destination city that someone starting in city 1 can reach while being younger than when they started.

The first line contains two integers $n$ ($1 \le n \le 5 \times 10^3$) and $m$ ($1 \le m \le 10^4$). The cities are numbered 1 to $n$, where city 1 is Orlando.

Each of the next $m$ lines describes one train line with four values:

• $s$ ($1 \le s \le n$): the starting city of the line
• $e$ ($1 \le e \le n$, $s \ne e$): the ending city of the line
• $t$ ($t =$ 'b' or 'r'): 'b' for a blue line, 'r' for a red line
• $a$ ($1 \le a \le 10000$): the number of minutes one ages (blue) or moves back in time (red) on this line

Print each destination city that someone starting in city 1 can reach while being younger than when they started, in increasing numerical order.