Телепорт
Тімур вирішив дослідити всесвіт. На його щастя він виявився дуже маленьким і складався з n планет. Для подорожей між планетами у часи Тімура використовувались паралельні всесвіти, яких всього було k. Для цього між деякими парами планет були двосторонні портали. На кожній планеті не більше одного порталу для кожного паралельного всесвіту. Перехід між планетами був миттєвим і не коштував нічого: мандрівник заходив у портал i-го всесвіту на планеті a, виходив з порталу i-го всесвіту на планеті b і випивав таблетку аспірину (навіть миттєве перебування у паралельному всесвіті викликало нестерпний головний біль, внаслідок так званого "ефекту Бахи"). Між порталами на одній планеті приходилось переміщуватись старим перевіреним способом - на фотонних дирижаблях. Вартість квитка на такий дирижабль була своя для кожної планети і кожної пари порталів на ній.
Тімур живе неподалеку від порталу 1 планети 1. Йому потрібно попасти до порталу k планети n, де його чекає його команда. Яку мінімальну кількість таблеток аспірину і суму в грошах він повинен взяти з собою щоб здійснити цю подорож? Здоров'я для Тімура важливіше матеріального багатства, тому він краще вип'є менше аспірину, навіть я що доведеться витратити більше грошей.
Вхідні дані
Перший рядок містить 3 цілих числа: n - кількість планет у всесвіті, m - кількість порталів між планетами та k - кількість паралельних світів (1 ≤ n ≤ 100, 1 ≤ k ≤ 11, 1 ≤ m ≤ 100000). Кожний з наступних m рядків містить по 3 цілих числа a, b, c - опис міжпланетного порталу: a, b - планети, з'єднані порталом (1 ≤ a, b ≤ n), c - номер паралельного всесвіту, що використовується порталом (1 ≤ c ≤ k). Далі йде n блоків по k рядків, кожен з яких містить k цілих чисел, - опис маршрутів фотонних дирижаблів на кожній планеті. k-й елемент j-го рядка i-го блоку - вартість квитка в тенге на дирижабль від порталу j до порталу k на планеті i. Вартості - цілі числа від 1 до 100. Числа в рядках відокремлені пропусками.
Вихідні дані
Два цілих числа, відокремлених проміжком: мінімальна кількість пігулок аспірину та мінімально можлива при цьому сума в тенге.