В \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}.