Легенди та міфи Південного Бутово#4161
У році 3141 Бутово стало вкрай непростим районом, але не через небезпеку, а завдяки курйозній проблемі: пустотливі роботизовані голуби захопили міські площі! Вони розігрують безневинні жарти над кожним, хто намагається змінити напрям на перехресті, чим неабияк ускладнюють навігацію мешканцям міста.
Бутово має проспектів, що йдуть з півночі на південь, і вулиць, що простягаються зі сходу на захід. Кожен проспект перетинається з кожною вулицею рівно в одному місці. Рух упродовж прямих ліній по проспектах чи вулицях — легкий та швидкий, однак повертати на перехрестях складно, адже там і збираються роботизовані голуби, щоб плутати мандрівників.
Для полегшення пересування громадян міська рада вирішила встановити на деяких перехрестях спеціальні навігаційні будки. У цих будках привітні гіди можуть безпечно та весело направити мандрівників, роблячи можливим зміну напрямку без втручання роботів-жартівників.
Однак бюджет міста в цьому році обмежений, бо мер фінансує грандіозний проект міського саду. Тож потрібно встановити мінімальну кількість будок із найменшою сумарною вартістю. Для належного функціонування необхідно розмістити будки так, щоб мешканці могли дістатись з будь-якого перехрестя до будь-якого іншого, змінюючи напрям лише в місцях із навігаційними будками.
Але й це ще не вся складність: на різних ділянках Бутово будівництво навігаційних будок коштує по-різному. Кожен район має центр, розташований на певному перехресті, а будь-яке інше перехрестя належить тому району, центр якого найближче до нього за особливою бутовською відстанню: це мінімальна кількість проміжних перехресть, через які треба пройти з одного в інше, плюс один. Якщо для деякого перехрестя центри кількох районів однаково віддалені, постійні зібрання голубів на такому перехресті унеможливлюють там встановлення будки.
Ваше завдання — знайти мінімальну вартість розміщення будок згідно з плануванням Бутово, щоб пересування між будь-якими двома перехрестями було можливим із поворотами лише у точках, де встановлені навігаційні будки.
У першому рядку введено три числа: , , — кількість проспектів, вулиць і районів Бутово відповідно (2 \leq N, M \leq 500, 1 \leq R \leq 1000). Далі йдуть рядків по три числа: номер проспекту й номер вулиці центру району, а також вартість будівництва будки у цьому районі. Проспекти й вулиці нумеруються з одиниці, усі вартості додатні й не перевищують тисячі. Центри районів не накладаються один на одного.
У першому рядку виведіть два числа: кількість перехресть , де потрібно встановити будки, і мінімальну сумарну вартість їхнього будівництва. У наступних рядках опишіть відповідні перехрестя: номер проспекту й номер вулиці для кожного з них. Якщо розмістити будки згідно з вимогами неможливо, виведіть одне число -1.
Приклад 1