Taxicab
In the city, taxis transport passengers along designated routes throughout the day. After reaching the last stop on a route, the taxi proceeds directly to the depot instead of returning to the first stop. Each stop is assigned a natural number ranging from 1 to a certain natural number n.
Your task is to develop a program that determines:
the completion time and the minimum travel cost for the fastest route;
the earliest completion time and the travel cost for the cheapest route.
Input
The first line contains the following natural numbers in this order:
n - the total number of stops, which does not exceed 250;
m - the number of available routes;
t - the number of minutes past the start of the day when the passenger begins their journey;
a - the stop number where the journey begins;
b - the stop number where the passenger wishes to arrive.
For each j from 1 to m, the (j + 1)-th line contains a triplet of numbers. Each triplet includes:
the first number (a natural number) - the stop number;
the second number (a natural number) - the arrival time in minutes from the start of the day at the specified stop for the taxi on the j-th route. It is assumed that at each stop, the taxi pauses for exactly one minute, during which passengers can board or alight;
the third number (a non-negative integer) - the fare from the previous stop (0 for the first stop of each route, positive for all subsequent stops).
The total number of segments across all routes does not exceed 7800.
Output
The first line should display, in order, the completion time and the minimum travel cost for the fastest route.
The second line should display, in order, the earliest completion time and the travel cost for the cheapest route.
For a valid solution, all these numbers must be less than 654321.