Таксомотор#7200

Таксомотор

1 секунда

64 мегабайти

Складна

У місті таксомотори розвозять пасажирів певними маршрутами протягом доби. З останньої зупинки маршруту таксомотор «їде в парк» (а не на першу зупинку). Всі зупинки занумеровано натуральними числами в межах від $1$ до деякого натурального $n$ .

Створіть програму, яка визначить:

час припинення подорожі й найменшу вартість подорожі для найшвидшого маршруту;
найменший час припинення подорожі й вартість подорожі для найдешевшого маршруту.

Вхідні дані

Перший рядок містить у вказаному порядку такі натуральні числа:

$n$ - кількість зупинок, що не перевищує $250$ ;

$m$ - кількість маршрутів;

$t$ - кількість хвилин від початку доби, коли пасажир починає свій рух;

$a$ - номер зупинки, з якої він починає свій рух;

$b$ - номер зупинки, на яку він хоче потрапити.

Для $j$ в межах від $1$ до $m$ включно $(j + 1)$ (j + 1)-ий рядок містить трійки чисел. У кожній такій трійці:

перше (натуральне) число - номер зупинки;
друге (натуральне) число - час прибуття у хвилинах від початку доби на вказану зупинку таксомотора, що їде $j$ -тим маршрутом. Вважається, що на кожній зупинці кожний таксомотор стоїть рівно хвилину, під час якої можна сісти на нього або зійти з нього;
третє (невід'ємне ціле) число - вартість проїзду від попередньої зупинки ( $0$ для першої зупинки кожного маршруту, додатне для всіх наступних зупинок).

Загальна кількість ланок всіх маршрутів не перевищує $7800$ .

Вихідні дані

Перший рядок має містити у вказаному порядку час припинення подорожі й найменшу вартість подорожі для найшвидшого маршруту.

Другий рядок має містити у вказаному порядку найменший час припинення подорожі й вартість подорожі для найдешевшого маршруту.

Для правильної відповіді усі ці числа менші за $654321$ .

Приклади

Приклад 1