Problems
Таксомотор
Таксомотор
У мiстi таксомотори розвозять пасажирiв певними маршрутами протягом доби. З останньої зупинки маршруту таксомотор <<їде в парк>> (а не на першу зупинку). Всi зупинки занумеровано натуральними числами в межах вiд \textbf{1} до деякого натурального \textbf{n}.
Створiть програму, яка визначить:
\begin{itemize}
\item час припинення подорожi й найменшу вартiсть подорожi для найшвидшого маршруту;
\item найменший час припинення подорожi й вартiсть подорожi для найдешевшого маршруту.
\end{itemize}
\InputFile
Перший рядок мiстить у вказаному порядку такі натуральнi числа:
\textbf{n} - кiлькiсть зупинок, що не перевищує \textbf{250};
\textbf{m} - кiлькiсть маршрутiв;
\textbf{t} - кiлькiсть хвилин вiд початку доби, коли пасажир починає свiй рух;
\textbf{a} - номер зупинки, з якої вiн починає свiй рух;
\textbf{b} - номер зупинки, на яку вiн хоче потрапити.
Для \textbf{j} в межах вiд \textbf{1} до \textbf{m} включно (\textbf{j} + \textbf{1})-ий рядок мiстить трiйки чисел. У кожнiй такiй трiйцi:
\begin{itemize}
\item перше (натуральне) число - номер зупинки;
\item друге (натуральне) число - час прибуття у хвилинах вiд початку доби на вказану зупинку таксомотора, що їде \textbf{j}-тим машрутом. Вважається, що на кожнiй зупинцi кожний автобус стоїть рiвно хвилину, пiд час якої можна сiсти на нього або зiйти з нього;
\item третє (невiд'ємне цiле) число - вартiсть проїзду вiд попередньої зупинки (\textbf{0} для першої зупинки кожного маршруту, додатне для всiх наступних зупинок).
\end{itemize}
Загальна кiлькiсть ланок всiх маршрутiв не перевищує \textbf{7800}.
\OutputFile
Перший рядок має містити у вказаному порядку час припинення подорожi й найменшу вартiсть подорожi для найшвидшого маршруту.
Другий рядок має містити у вказаному порядку найменший час припинення подорожi й вартiсть подорожi для найдешевшого маршруту.
Для правильної відповіді усі ці числа менші за \textbf{654321}.
Input example #1
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
Output example #1
70 12 1510 2