Тимур решил поиследовать вселенную. На его счастье она оказалось очень маленькой и состояла из n планет. Для путешествия между планетами во времена Тимура использовались параллельные вселенные, которых всего было k. Для этого между некоторыми парами планет имелись двусторонние порталы. На каждой планете не более одного портала для каждой параллельной вселенной. Переход между планетами был мгновенным и не стоил ничего: путешественник заходил в портал i-й вселенной на планете a, выходил из портала i-й вселенной на планете b и выпивал таблетку аспирина (даже мгновенное пребывание в параллельной вселенной вызывало невыносимую головную боль, вследствие так называемого "эффекта Бахи"). Между порталами на одной планете приходилось перемещаться старым проверенным способом - на фотонных дирижаблях. Стоимость билета на такой дирижабль была своя для каждой планеты и каждой пары порталов на ней.
Тимур живет недалеко от портала 1 планеты 1. Ему надо попасть к порталу k планеты n, где его ждет его команда. Какое минимальное количество таблеток аспирина и сумму в тенге он должен взять с собой чтобы совершить это путешествие? Здоровье для Тимура важнее материального богатства, поэтому он лучше выпьет меньше аспирина, даже если придется потратить больше денег.
The first line contains 3 integers: n - the number of planets in the universe, m - the number of portals between the planets and k - the number of parallel universes (1 ≤ n ≤ 100, 1 ≤ k ≤ 11, 1 ≤ m ≤ 100000). Each of the next m lines contains 3 integers a, b, c - the description of the interplanetary portal: a, b - the planets, connected with a portal (1 ≤ a, b ≤ n), c - the number of the parallel universe, used by the portal (1 ≤ c ≤ k). Далее идут n блоков по k строк, каждая из которых содержит k целых чисел, - описание маршрутов фотонных дирижаблей на каждой планете. k-й элемент j-й строки i-го блока - стоимость билета в тенге на дирижабль от портала j к порталу k на планете i. Стоимости - целые числа от 1 до 100. Числа в строках разделены пробелами.
Два целых числа, разделенных пробелом: минимальное количество таблеток аспирина и минимально возможная при этом сумма в тенге.