Тимур решил поиследовать вселенную. На его счастье она оказалось очень маленькой и состояла из \textbf{n} планет. Для путешествия между планетами во времена Тимура использовались параллельные вселенные, которых всего было \textbf{k}. Для этого между некоторыми парами планет имелись двусторонние порталы. На каждой планете не более одного портала для каждой параллельной вселенной. Переход между планетами был мгновенным и не стоил ничего: путешественник заходил в портал \textbf{i}-й вселенной на планете \textbf{a}, выходил из портала \textbf{i}-й вселенной на планете \textbf{b} и выпивал таблетку аспирина (даже мгновенное пребывание в параллельной вселенной вызывало невыносимую головную боль, вследствие так называемого "\textit{эффекта Бахи}"). Между порталами на одной планете приходилось перемещаться старым проверенным способом - на фотонных дирижаблях. Стоимость билета на такой дирижабль была своя для каждой планеты и каждой пары порталов на ней. Тимур живет недалеко от портала \textbf{1} планеты \textbf{1}. Ему надо попасть к порталу \textbf{k} планеты \textbf{n}, где его ждет его команда. Какое минимальное количество таблеток аспирина и сумму в тенге он должен взять с собой чтобы совершить это путешествие? Здоровье для Тимура важнее материального богатства, поэтому он лучше выпьет меньше аспирина, даже если придется потратить больше денег. \InputFile Первая строка содержит \textbf{3} целых числа: \textbf{n} - количество планет во вселенной, \textbf{m} - количество порталов между планетами и \textbf{k} - количество параллельных вселенных (\textbf{1} ≤ \textbf{n} ≤ \textbf{100}, \textbf{1} ≤ \textbf{k} ≤ \textbf{11}, \textbf{1 }≤ \textbf{m} ≤ \textbf{100000}). Каждая из следующих \textbf{m} строк содержит по \textbf{3} целых числа \textbf{a}, \textbf{b}, \textbf{c} - описание межпланетного портала: \textbf{a}, \textbf{b} - планеты, соединенные порталом (\textbf{1} ≤ \textbf{a}, \textbf{b} ≤ \textbf{n}), \textbf{c} - номер параллельной вселенной, используемой порталом (\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 Два целых числа, разделенных пробелом: минимальное количество таблеток аспирина и минимально возможная при этом сумма в тенге.