У \textbf{3141} році Бутово перетворилось у дуже небезпечний район, наповнени вбивцями та іншими жуліками. Настільки небезпечний, що стало страшно переміщуватись навіть на танкі! Нагадаємо, що Бутово складається з \textbf{N} проспектів, які йдуть у напрямку з півночі на південь, та \textbf{M} вулиць, які йдуть зі сходу на захід. Кожен проспект перетинається з кожною вулицею рівно на одному перехресті. Переміщення вздовж проспекту чи вулиці на високій швидкості безечно, а поворот де-небудь, навпаки, дуже небезпечний, так як для цього приходиться знижувати швидкість, і у той же момент вас починають атаковати угрупування місцевих жителів. Управління поліцією Бутово вирішило трохи виправити ситуацію. Керівники управління вирішили, що можна поставити декілька постів на деяких перехрестях, щоб на них жителі могли спокійно повертати, не боючись бути атакованими, так як поліція вже взяла на озброєння новітні гвинтівки "Мушкет-1812" і, у випадку чого-небудь, зможе захистить честь та гідність кожного законослухняного громадянина. На жаль, саме у цьому році начальник управління вирішив побудувати собі новий елітний маєток, тому управління вирішило потратити якомога менше грошей на будівництво нових постів. Проте, щоб усе виглядало чистенько, необхідно побудувати пости так, щоб можна було дістатись від довільного перехрестя до довільного іншого, повертаючи лише на спеціально обладнаних постах. Інакше нагряне перевірка і усіх звільнять. На цьому проблеми Бутово не завершились. Деякі райони Бутово є більш небезпечними, і пости, які будуть побудовані у більш небезпечних районах, стоять дорожче. У кожного района є центр, який знаходиться поблизу деякого перехрестя. Довільне інше перехрестя належить району, центр якого є найближчим до перехрестя. Відстань між перехрестями вимірюється при допомозі так званої Бутовської відстані: відстань між двома перехрестями - це мінімальна кількість проміжних перехресть, які потрібно подолати, щоб потрапити з одного району в інший, плюс один. Якщо ж існує декілька районих центрів, які знаходяться на мінімальній відстані від деякого перехрестя, то на цьому перехресті постійно відбуваються сутички двох авторитетів, тому на цьому перехресті побудувати пост неможливо. Вам потрвбно, знаючи розміщення районів Бутово, визначити мінімальну вартість побудови поствв так, щоб можна було безпечно дістатись від довільного перехрестя до довільного іншого. \InputFile Перший рядок вхідного файлу містить три числа \textbf{N}, \textbf{M}, \textbf{R} - кількість проспектів, кількість вулиць та кількість районів у Бутово, відповідно (\textbf{2} ≤ \textbf{N}, \textbf{M} ≤ \textbf{500}, \textbf{1} ≤ \textbf{R} ≤ \textbf{1000}). Наступні \textbf{R} рядків містять по три цілих числа - номер проспекту та номер вулиці, на яких розміщено центр відповідного району, і вартість побудови поста у цьому районі. Проспекти та вулиці нумеруються з одиниці, вартість побудови скрізь додатна і не перевищує однієї тисячі. Ніякі два райони не мають співпадаючих центрів. \OutputFile У першому рядку вихідного файлу виведіть два числа: кількість перехресть \textbf{K}, на яких варто побудувати пости, та знайдену мінімальну сумарну вартість побудови. У наступних \textbf{K} рядках повинні міститись описи знайдених перехрестьв: номер проспекту та номер вулиці, на перетині яких розміщено відповідне перехрестя. Якщо пости потрібним чином розмістити неможливо, виведіть у вихідний файл єдине число \textbf{-1}.