Problem E
Road Trip!

If you’ve done the practice exams, you probably remember Alice, the MPCS student who uses the power of algorithms to plan her mountain hikes. As it turns out, Alice also loves going on road trips! The way that Alice comes up with her road trip itinerary is governed by three simple rules:

• Rule #1: When Alice is done visiting a city, she will drive to the city that requires the shortest driving time.

• Rule #2: Alice is open to visiting the same city multiple times during a road trip, but enough time must’ve passed since her last visit to that city to make the visit worthwhile. In other words, Alice won’t drive to a city if she already visited that city recently.

• Rule #3: Alice won’t travel indefinitely: she has a maximum duration in mind for the road trip, and she’ll stop the road trip if visiting a city will put her over that limit (or if there are no cities she can travel to from her current city).

In this problem, you will write a program that produces a road trip itinerary according to these rules.

More specifically, we will assume that there are $N$ cities numbered $0,1,\ldots ,N-1$. Every city $i$ has three values we care about:

• $s_ i$ is a string with the name of the city (e.g., Chicago). Take into account that $s_ i$ is used only for display purposes; it does not uniquely identify a city.

• $t_ i$ is the time (in hours) required to visit that city.

• $v_ i$ represents the last time we visited that city. We set this value initially to $-1$ for all cities, to indicate the cities have not yet been visited.

A road between cities is specified as a tuple $(c_\textrm {from}, c_\textrm {to}, d)$, where $c_\textrm {from}$ and $c_\textrm {to}$ are the two cities connected by the road, and $d$ is the time (in hours) required to drive from $c_\textrm {from}$ to $c_\textrm {to}$. We refer to $R$ as the set of all roads, and to $|R|$ as the number of roads. Take into account that all roads are bidirectional, and that $R$ contains one tuple per road, not one tuple per direction (e.g., if $R$ contains $(3,5,7)$, this implies that I can drive from city $3$ to city $5$ in $7$ hours and from city $5$ to city $3$ in the same amount of time). For simplicity, we will assume that there is, at most, one road connecting any pair of cities.

Before planning a road trip, Alice decides on three important values: $S$, the city that the road trip will start in, $M$, the maximum duration of the road trip, and $H$, the minimum amount of time that must pass before Alice considers visiting a city again. During the road trip, Alice keeps track of the current time $T$. For simplicity, we assume that Alice counts time in hours, and that only two things can alter $T$: travelling from one city to another, and visiting a city. At the start of the road trip, $T=0$. However, since Alice always visits the first city on her road trip, $T$ will always advance to $t_ S$ (the time required to visit city $S$) at the start of the road trip.

After visiting a city $i$, Alice updates the value of $v_ i$ to be equal to $T$, and must then decide the next city to visit. She looks at all the roads connected to $i$, and discards the ones that would break any of her road trip rules. More specifically, for any given road, if $j$ is the city connected by that road:

• Rule #2: If the time at which Alice arrives at $j$, minus $v_ j$, is less than $H$, then Alice discards this road.

• Rule #3: If the time at which Alice would be done visiting $j$ is greater than $M$, then Alice discards this road.

If, after applying these rules, there are multiple roads to choose from, then Alice applies Rule #1 and chooses the one with the shortest driving time (if there are multiple roads with the same shortest time, Alice chooses the destination city with the lowest number). Once Alice chooses a road, we add two values to $T$: the driving time $d$ for that road, and the time to visit the destination city, $v_ j$.

If, on the other hand, there are no roads left to consider, Alice ends the road trip. At the end of this algorithm, we are interested in knowing the sequence of cities that Alice will visit (and, specifically, their string representations), and the time at which the road trip ended.

Consider the following example where $N=5$, $s_ i=(\texttt{A},\texttt{B},\texttt{C},\texttt{D},\texttt{E})$, $t_ i=(10,10,20,15,10)$, $S=0$, $M=120$, $H=50$, and $R=\{ (0,1,5),(0,4,20),(1,2,10),(1,3,15),(1,4,15),(2,3,5),(3,4,5)\} $. You can find below the progress of Alice’s road trip. Note that we refer in this example to cities by their names (A,B,…), and that the diagrams show the state of all the values after visiting the city highlighted in gray.

$S=0$, so we start in city A. This city takes $10$ hours to visit, so $T=10$ after we visit the city. From this city, we can go to either B or E, neither of which we have visited previously. However, the time to reach B is smaller, so we go to that city.

We advance $T$ by $5$ (the time to travel to B) and by $10$ ($t_1$, the time to visit B), which brings $T$ to $25$. We can go to A, C, D, or E. We exclude A because we visited it too recently. More specifically, we could get to A at time $30$, but at that time it will have been $20$ hours since we last visited A, which is less that $H$ (50). Of the remaining cities, we pick C because it has the shortest driving time.

After visiting C, we choose to go to D. Notice how, even if the driving time to B had been shorter than the driving time to D, we can’t consider B because we’ve visited it too recently.

Similarly, after visiting D, our only option is to visit E next.

After visiting E, we can’t go back to D, but it has been long enough since we last visited A and B. More specifically, we could get to A at time $110$ and to B at time $105$. The time since we last visited each would be $100$ and $80$, respectively, both of which are greater than $H$ ($50$). We choose B because it has the shortest driving time.

After visiting B, $T=115$. We cannot visit any more cities, because travelling to any of them would make us go over our maximum road trip duration $M$ ($120$). So, the road trip ends here, after visiting A, B, C, D, E, and B, in that order.

Input

The input begins with a line containing five integers: $N$, $|R|$, $H$, $M$, and $S$, all as previously defined, and each separated from the previous by a single space.

The input is followed by $N$ lines, one per city. Each such line contains three values: an integer $i$ (the number of the city) followed by a string $s_ i$ and an integer $t_ i$, as previously defined. The first city always has a value of $i=0$, and the number is always increased by one in each subsequent line.

The input is followed by $|R|$ lines, one per road. Each such line contains three integers: $c_\textrm {from}$, $c_\textrm {to}$, $d$, as previously defined.

You may assume the following bounds:

• $1 \leqslant N \leqslant 200$

• $0 \leqslant |R| \leqslant \frac{N\cdot (N-1)}{2}$.

• $0 \leqslant S, c_\textrm {from}, c_\textrm {to} \leqslant N-1$

• $0 \leqslant H \leqslant 2^{32}-1$

• $t_ S \leqslant M \leqslant 2^{32}-1$ (where $t_ S$ is the time required to visit the first city $S$)

• $1 \leqslant d \leqslant 2^{32}-1$

• $s_ i$ has a length of at least one and at most ten characters, and is composed only of lowercase and uppercase English letters.

• $1 \leqslant t_ i \leqslant 2^{32}-1$

Note that the first sample input correspond to the example road trip described above. The second sample input uses the same values, except with $M=200$ and with longer city names.

Output

Print two lines. The first line contains the values of $s_ i$ for the cities that were visited in the road trip, in the order in which they were visited. Each $s_ i$ should be separated from the previous by a single space. The second line contains a single integer: the value of $T$ when the road trip ended.

5 7 50 120 0
0 A 10
1 B 10
2 C 20
3 D 15
4 E 10
0 1 5
0 4 20
1 2 10
1 3 15
1 4 15
2 3 5
3 4 5

A B C D E B
115

5 7 50 200 0
0 Alfa 10
1 Bravo 10
2 Charlie 20
3 Delta 15
4 Echo 10
0 1 5
0 4 20
1 2 10
1 3 15
1 4 15
2 3 5
3 4 5

Alfa Bravo Charlie Delta Echo Bravo Alfa Echo Delta
180