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