Таксомотор
У м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.