eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Телепорт

Телепорт

Лимит времени 2 секунды
Лимит использования памяти 64 MiB

Тимур решил поиследовать вселенную. На его счастье она оказалось очень маленькой и состояла из n планет. Для путешествия между планетами во времена Тимура использовались параллельные вселенные, которых всего было k. Для этого между некоторыми парами планет имелись двусторонние порталы. На каждой планете не более одного портала для каждой параллельной вселенной. Переход между планетами был мгновенным и не стоил ничего: путешественник заходил в портал i-й вселенной на планете a, выходил из портала i-й вселенной на планете b и выпивал таблетку аспирина (даже мгновенное пребывание в параллельной вселенной вызывало невыносимую головную боль, вследствие так называемого "эффекта Бахи"). Между порталами на одной планете приходилось перемещаться старым проверенным способом - на фотонных дирижаблях. Стоимость билета на такой дирижабль была своя для каждой планеты и каждой пары порталов на ней.

Тимур живет недалеко от портала 1 планеты 1. Ему надо попасть к порталу k планеты n, где его ждет его команда. Какое минимальное количество таблеток аспирина и сумму в тенге он должен взять с собой чтобы совершить это путешествие? Здоровье для Тимура важнее материального богатства, поэтому он лучше выпьет меньше аспирина, даже если придется потратить больше денег.

Входные данные

Первая строка содержит 3 целых числа: n - количество планет во вселенной, m - количество порталов между планетами и k - количество параллельных вселенных (1n100, 1k11, 1 m100000). Каждая из следующих m строк содержит по 3 целых числа a, b, c - описание межпланетного портала: a, b - планеты, соединенные порталом (1a, bn), c - номер параллельной вселенной, используемой порталом (1ck). Далее идут n блоков по k строк, каждая из которых содержит k целых чисел, - описание маршрутов фотонных дирижаблей на каждой планете. k-й элемент j-й строки i-го блока - стоимость билета в тенге на дирижабль от портала j к порталу k на планете i. Стоимости - целые числа от 1 до 100. Числа в строках разделены пробелами.

Выходные данные

Два целых числа, разделенных пробелом: минимальное количество таблеток аспирина и минимально возможная при этом сумма в тенге.

Пример

Входные данные #1
2 1 4
1 2 3
0 2 5 0
0 0 2 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 2
0 2 0 5
0 0 0 0
Выходные данные #1
1 8