Новый год

Санта Клаус решил сделать новогодний подарок своим эльфам. Конечно же, Санта был бы не Санта, если бы его подарок был обыкновенным. Подарок просто замечательный - эльфы идут в кино!

Конечно же, если все эльфы пойдут в кино одновременно, это может показаться кому-нибудь подозрительным. Ну, вы понимаете, некоторые люди все еще не верят в эльфов. Так что каждый день ровно одна пара эльфов пойдет в кино. Конечно, идти в кино самому по себе неинтересно, гораздо интереснее пойти с другом или подругой. Таким образом, каждый день один мальчик-эльф и одна девочка-эльф вместе пойдут в кино.

Но эльфы, они такие разные. Каждый эльф четко знает, с какими эльфами и на какой фильм он или она хотели бы пойти. Поскольку у каждой пары эльфов свои взаимоотношения, для каждой пары, которая согласна вместе пойти в кинотеатр, известно какой именно фильм они хотели бы посмотреть.

Но на самом деле все еще хуже. Дело в том, что билеты в кино стоят денег. Конечно, Санта не беден, но ему нужно много денег на подарки детям. Так что собрав у эльфов пожелания, кто куда и с кем хотел бы пойти в кино, Санта решил удовлетворить некоторые пожелания таким образом, чтобы потратив как можно меньше денег, добиться того, что каждый эльф хотя бы один раз побывает в кино.

Помогите Санте, он пока не до конца освоился с компьютером.

Входные данные

Первая строка входного файла INPUT.TXT содержит два целых числа n и m - количество мальчиков-эльфов и девочек-эльфов, соответственно (1 ≤ n, m ≤ 100). Вторая строка содержит r – количество пожеланий, которое Санта получил от своих эльфов (1 ≤ r ≤ 1500). Следующие r строк содержат по три целых числа a_i, b_i и c_i каждая. Числа означают, что мальчик-эльф a_i хотел бы пойти в кино с девочкой-эльфом b_i, и билет на фильм, на который они хотели бы пойти, стоит c_i (1 ≤ c_i ≤ 1000). Каждый эльф хочет пойти в кино хотя бы с одним другим эльфом.

Выходные данные

На первой строке выходного файла OUTPUT.TXT выведите минимальную сумму, которую Санте придется потратить, чтобы сделать своим эльфам подарок. На второй строке выведите k - количество билетов, которое Санта должен купить. Наконец, третья строка должна содержать k целых чисел – номера пожеланий, которые следует удовлетворить.

Пример

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]