Bad Roads#4956
In a country, there are several cities connected by roads. Due to an insufficient budget, some roads are covered with potholes, so certain cars cannot use certain roads. Each road has an associated height — the minimal height of the bottom of a car that can drive through that road. Additionally, some roads are private, and one must pay to use them. The toll for each such road is standardized and equals one standard unit. For each such road, the required travel time is also known.
You must drive from city to city using no more than minutes and no more than standard units. Find the minimal height of the car’s bottom that makes the trip possible.
The first line contains the number of cities (1 \leq n \leq 100), the number of roads (1 \leq m \leq 10^4), the starting city , and the ending city (1 \leq s, t \leq n). The second line contains (0 \leq \text{money} \leq 10^6) and (0 \leq \text{maxtime} \leq 10^6).
Each of the next lines describes a road in the format: u_i v_i c_i t_i h_i. Here, u_i is the starting city of the -th road, v_i is the ending city, c_i is if the road is private (and otherwise), t_i is the travel time for the road, and h_i is the required car bottom height (1 \leq u_i, v_i \leq n, 0 \leq t_i \leq 10^4, 0 \leq h_i \leq 10^6). All roads are one-way. All numbers in the input are integers.
If there is no way to drive from to under the given restrictions, output -1. Otherwise, output, in the first line, the minimal required car bottom height; in the second line, the number of roads in the chosen route; and in the third line, the indices (from to , in the order of input) of the roads used to travel from to , in the order they are taken.
Example 1