Таксомотор
Таксомотор
У мiстi таксомотори розвозять пасажирiв певними маршрутами протягом доби. З останньої зупинки маршруту таксомотор «їде в парк» (а не на першу зупинку). Всi зупинки занумеровано натуральними числами в межах вiд 1 до деякого натурального n.
Створiть програму, яка визначить:
час припинення подорожi й найменшу вартiсть подорожi для найшвидшого маршруту;
найменший час припинення подорожi й вартiсть подорожi для найдешевшого маршруту.
Вхідні дані
Перший рядок мiстить у вказаному порядку такі натуральнi числа:
n - кiлькiсть зупинок, що не перевищує 250;
m - кiлькiсть маршрутiв;
t - кiлькiсть хвилин вiд початку доби, коли пасажир починає свiй рух;
a - номер зупинки, з якої вiн починає свiй рух;
b - номер зупинки, на яку вiн хоче потрапити.
Для j в межах вiд 1 до m включно (j + 1)-ий рядок мiстить трiйки чисел. У кожнiй такiй трiйцi:
перше (натуральне) число - номер зупинки;
друге (натуральне) число - час прибуття у хвилинах вiд початку доби на вказану зупинку таксомотора, що їде j-тим машрутом. Вважається, що на кожнiй зупинцi кожний автобус стоїть рiвно хвилину, пiд час якої можна сiсти на нього або зiйти з нього;
третє (невiд'ємне цiле) число - вартiсть проїзду вiд попередньої зупинки (0 для першої зупинки кожного маршруту, додатне для всiх наступних зупинок).
Загальна кiлькiсть ланок всiх маршрутiв не перевищує 7800.
Вихідні дані
Перший рядок має містити у вказаному порядку час припинення подорожi й найменшу вартiсть подорожi для найшвидшого маршруту.
Другий рядок має містити у вказаному порядку найменший час припинення подорожi й вартiсть подорожi для найдешевшого маршруту.
Для правильної відповіді усі ці числа менші за 654321.
Приклад
7 4 1 7 3 3 2 0 4 35 1 2 50 1 3 70 1 5 5 0 6 15 1 4 30 1 5 45 1 7 2 0 2 5 11 6 10 1 7 20 1 7 60 0 2 70 1 6 80 1 7 90 1
70 12 1510 2