Тімур вирішив дослідити всесвіт. На його щастя він виявився дуже маленьким і складався з \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 Два цілих числа, відокремлених проміжком: мінімальна кількість пігулок аспірину та мінімально можлива при цьому сума в тенге.