Чтобы стать взрослым гномом, нужно пройти страшный-страшный лабиринт. Лабиринт настолько запутанный и опасный, что гномиков в него надо пускать парами. Конечно же, пара должна состоять из мальчика и девочки. Поскольку бывает разное количество мальчиков и девочек, кому-то придётся проходить лабиринт несколько раз (главное, чтобы гномик прошёл его хотя бы раз). Для каждой пары мальчик-девочка, которые дружат между собой, взрослые гномы знают время, за которое эта парочка найдёт выход из лабиринта. Помогите им провести всех детей через лабиринт за минимально возможное время. \InputFile Первая строка входного файла содержит два целых числа \textbf{n} и \textbf{m} - количество мальчиков и девочек у гномиков соответственно (\textbf{1} ≤ \textbf{n}, \textbf{m} ≤ \textbf{100}), вторая строка содержит число \textbf{r} - количество пар, которых можно пускать вместе (\textbf{1} ≤ \textbf{r} ≤ \textbf{1000}). Следующие \textbf{r} строк содержат по три числа каждая: \textbf{a_i}, \textbf{b_i} и \textbf{c_i}. Эти числа означают, что мальчик с номером \textbf{a_i} может пойти в лабиринт с девочкой с номером \textbf{b_i}, и они пробудут там вместе \textbf{c_i} секунд (\textbf{1} ≤ \textbf{c_i} ≤ \textbf{1000}). Гарантируется, что у каждого гномика есть друг (подруга), с которым(ой) она(он) может пойти в лабиринт. \OutputFile В первой строке выходного файла выведите минимальное время, за которое можно провести посвящение. На второй строке выведите \textbf{k} - количество пар, которые следует пустить в лабиринт. Третья строка должна содержать \textbf{k} целых чисел - номера этих пар, как они заданы во входном файла.